# MERLIN: Multimodal Embedding Refinement via LLM-based Iterative Navigation
for Text-Video Retrieval-Rerank Pipeline

Donghoon Han1111, Eunhwan Park1111,
Gisang Lee2111, Adam Lee3, 4, Nojun Kwak5222
1Buzzni AI Lab, 2KAIST, 3UC Berkeley,
4Wrtn, 5Seoul National University
{owen<EMAIL_ADDRESS><EMAIL_ADDRESS>
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The rapid expansion of multimedia content has made accurately retrieving
relevant videos from large collections increasingly challenging. Recent
advancements in text-video retrieval have focused on cross-modal interactions,
large-scale foundation model training, and probabilistic modeling, yet often
neglect the crucial user perspective, leading to discrepancies between user
queries and the content retrieved. To address this, we introduce MERLIN
(Multimodal Embedding Refinement via LLM-based Iterative Navigation), a novel,
training-free pipeline that leverages Large Language Models (LLMs) for
iterative feedback learning. MERLIN refines query embeddings from a user
perspective, enhancing alignment between queries and video content through a
dynamic question answering process. Experimental results on datasets like MSR-
VTT, MSVD, and ActivityNet demonstrate that MERLIN substantially improves
Recall@1, outperforming existing systems and confirming the benefits of
integrating LLMs into multimodal retrieval systems for more responsive and
context-aware multimedia retrieval111Code will be released upon acceptance..

MERLIN: Multimodal Embedding Refinement via LLM-based Iterative Navigation for
Text-Video Retrieval-Rerank Pipeline

Donghoon Han1111, Eunhwan Park1111, Gisang Lee2111, Adam Lee3, 4, Nojun
Kwak5222 1Buzzni AI Lab, 2KAIST, 3UC Berkeley, 4Wrtn, 5Seoul National
University {owen<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

††footnotetext: 111 Equal contribution.††footnotetext: 222 Corresponding
author.

##  1 Introduction

Multimedia content has recently grown rapidly in both quantity and quality,
making the task of finding relevant videos from vast collections increasingly
challenging. While recent studies on text-video retrieval have primarily
focused on cross-modal interaction Wang et al. (2023); Huang et al. (2023); Wu
et al. (2023); Jin et al. (2023), large-scale foundation model training Chen
et al. (2024b, 2023); Zhao et al. (2024); Wang et al. (2024a) and
probabilistic modeling Hao et al. (2023); Fang et al. (2023); Hao and Zhang
(2023), there remains a notable lack of consideration for the discrepancy in
text-video retrieval. For instance, as illustrated in Figure 1, the video
caption “a baby playing with a cat’s tail” fails to fully capture the
additional context of a playful interaction between the baby and the cat. In
real-world scenarios, such discrepancies often arise because users tend to
submit succinct queries that do not capture the full context of the videos
related to their search intent. Consequently, this mismatch can lead to
unsatisfactory retrieval performance. Moreover, neglecting the user
perspective, making users to refine their natural language query for multiple
times to fully reflect their search intent, degrades the quality of user
experience and makes it difficult to understand the search intent, leading to
a discrepancy between user queries and the information within the retrieved
videos.

Figure 1: An illustration of the discrepancy between the video caption which
could be treated as a user query and the video from MSR-VTT dataset. blue and
red indicate the additional details within the video frame, and those
reflecting temporal information, respectively.

To address this issue, we introduce MERLIN (Multimodal Embedding Refinement
via LLM-based Iterative Navigation), a novel training-free and iterative
feedback learning pipeline that leverages the power of Large Language Models
(LLMs) to augment queries based on the user perspective, thereby mitigating
the aforementioned discrepancies and significantly improving the text-video
retrieval performance. Inspired by human problem-solving and cognitive
feedback mechanisms Flower and Hayes (1981); Doherty and Balzer (1988), we
employ an interactive and iterative feedback learning Böhm et al. (2019);
Stiennon et al. (2020); Ziegler et al. (2019); Wu et al. (2020); Ouyang et al.
(2022); Glaese et al. (2022); Akyürek et al. (2023); Madaan et al. (2023); Lee
et al. (2024); Liang et al. (2024) consisting of a question-and-answer process
that iteratively refines query embeddings for text-video retrieval. Moreover,
to our best knowledge, MERLIN presents the first implementation of a
retrieval–rerank pipeline in the domain of text-video retrieval, establishing
a novel framework that prioritizes user intention and interaction in refining
search results.

The primary strength of MERLIN lies in its capability to iteratively adapt and
refine query embeddings without necessitating the costly re-training of pre-
trained models. By generating a series of questions based on the metadata and
content of the top-retrieved video and answering the question through LLMs,
MERLIN iteratively refines query embedding with answer embedding, thereby
enhancing semantic relevance of queries and the information contained within
the videos. Experimental results on benchmark datasets, including MSR-VTT,
MSVD, and ActivityNet, demonstrate the superiority of the retrieval
performance (e.g. Recall@K) by showing significant improvement. Specifically,
MERLIN boosts text-video retrieval performance (Recall@1) of Google Multimodal
Embedding from $44.00$ to $78.00$ on MSR-VTT, from $52.39$ to $77.61$ on MSVD
and from $56.58$ to $68.44$ on ActivityNet.

The key contributions of our paper are as follows: (1) Introduction of MERLIN,
a novel LLM-based framework for multimodal embedding refinement that addresses
discrepancies between user queries and video content by integrating user
perspectives. (2) Implementation of an iterative, cost-effective method for
refining query embeddings using LLMs, significantly reducing computational
demands while improving retrieval accuracy. (3) Presentation of the first
retrieval-rerank pipeline in text-video retrieval, enhancing interactivity and
context-awareness within multimodal systems. (4) Experimental results shows
that MERLIN substantially improves Recall@1 on MSR-VTT, MSVD and ActivityNet,
thereby demonstrating notable enhancements in zero-shot text-video retrieval.

Figure 2: An illustration of MERLIN for text-video retrieval. The yellow arrow
represents the LLM Questioner returning a question for next round based on
metadata of anchor video (Section 3.3). The green arrow represents the human-
simulating LLM agent returning an answer based on the “video in mind” through
Question Answering module and Aggregation module (Section 3.4). The pink arrow
represents MERLIN returning a retrieved video candidates through Multimodal
Encoder and Reranker (Section 3.5). The system initially retrieves video
candidates $\hat{v}^{0}$ based on the input query text $q$ using a pre-trained
multimodal encoder. Using anchor video, LLM Question Generator produces a
question $\hat{q}^{1}$ to elicit additional information from the user (Section
3.3). The LLM Agent answers this question based on the “video in mind”,
mimicking the human feedback process $\tilde{a}^{1}$. The query and answer
embeddings are then gradually integrated for each round. The updated query
embedding is used to rerank the video candidates $\hat{v}^{1}$, and the
process repeats for multiple rounds.

##  2 Related Works

##### Dataset.

Text-to-video retrieval aims to retrieve relevant videos based on natural
language descriptions and several benchmark video datasets Anne Hendricks et
al. (2017); Caba Heilbron et al. (2015); Chen and Dolan (2011); Xu et al.
(2016) have been curated for this task. One notable dataset is ActivityNet
Caba Heilbron et al. (2015), which consists of video-text pairs capturing
various human activities. Another widely used dataset is MSR-VTT Xu et al.
(2016), which comprises open-domain web videos paired with natural language
descriptions. These datasets provide a diverse range of video content and
textual queries, enabling comprehensive evaluation of retrieval systems.

##### Method.

Prior studies have focused on cross-modal interaction, large-scale foundation
model training, and probabilistic modeling. In cross-modal interaction Wang et
al. (2023); Huang et al. (2023); Jin et al. (2023) have enhanced reasoning
abilities by capturing cross-modal similarities at multiple granularity
levels, introduced efficient video prompt mechanisms Lester et al. (2021) with
minimal trainable parameters, and improved retrieval with strategies like
Disentangled Conceptualization and Set-to-Set Alignment. In foundation model
training Chen et al. (2024b, 2023); Zhao et al. (2024); Wang et al. (2024a)
significant advances have been made with the development of large-scale video
and vision-language models leveraging extensive web data, and fine-tuning
techniques for better performance on downstream tasks. In probabilistic
modeling Hao et al. (2023); Fang et al. (2023); Hao and Zhang (2023), novel
alignment methods and modeling of video and text representations as
probabilistic distributions have been proposed to improve text-video retrieval
accuracy and address domain adaptation challenges.

Concurrent to prior studies and our work, Levy et al. (2023) proposed a chat-
based image retrieval system (ChatIR) that interacts with users through
conversation to gather additional information beyond the initial query, aiming
to better understand and clarify the user’s search intent. Different from
ChatIR, MERLIN incorporates frame-level answer generation tailored to the
specific requirements of text-video retrieval, employing a training-free
approach. Furthermore, inspired by Composed Image Retrieval Liu et al. (2021);
Jang et al. (2024), we iteratively refine the embedding by employing spherical
linear interpolation, instead iteratively concatenate question and answer pair
and feed into retrieval model. Lastly, we handle both multi-modality data
simultaneously, meaning that our generation result would be more likely
aligned to user’s search intent. This iterative refinement process mirrors
human tendencies to continuously improve their queries based on interactive
feedback, akin to strategies seen in feedback-based refinement in textual
content. This approach is supported by the growing application of
reinforcement learning, which has been increasingly utilized to enhance the
quality of generated content through both reference-based and reference-
independent feedback mechanisms Böhm et al. (2019); Stiennon et al. (2020);
Ziegler et al. (2019); Wu et al. (2020); Ouyang et al. (2022); Glaese et al.
(2022); Akyürek et al. (2023); Madaan et al. (2023); Lee et al. (2024); Liang
et al. (2024).

##  3 Multimodal Embedding Refinement via LLM based Iterative Navigation

###  3.1 Retrieval Scenario

Figure 3: An article of scenario of Google Lens.

In this work, we consider a scenario where a user aims to find a specific
video in a search engine, having a firm intent and precise specifications in
mind for the desired video. We refer to this desired video as the “video in
mind” – an imagined video that the user seeks to retrieve, encompassing
various attributes such as visual content, context, and temporal dynamics.
However, expressing the full specifications of this “video in mind” through a
single query often leads to a discrepancy between the user’s intent and the
retrieved results, hindering the search experience.

We incorporate this “video in mind” scenario into the text-video retrieval
task, where the goal is to retrieve the most relevant video from a collection
based on the user’s textual query. Inspired by the success of multimodal
systems like Google Lens222https://lens.google/, which effectively handle and
integrate both image and text inputs, we propose MERLIN, an interactive
pipeline that dynamically elicits and incorporates user feedback to bridge the
gap between the user’s search intent and the retrieved video candidates.
MERLIN leverages the power of LLMs to simulate a human-like feedback process,
where a “human-simulating LLM agent” engages in a multi-turn conversation with
the user, asking clarifying questions and providing answers based on the
“video in mind” – the imagined video that the agent has in mind based on the
user’s initial query and subsequent feedback.

###  3.2 Background

Suppose that we have the query text $q\in\mathcal{Q}$, a video
$v\in\mathcal{V}$, where $\mathcal{Q}$ and $\mathcal{V}$ indicate a set of
queries and videos. Using a pre-trained multimodal encoder $f_{\text{enc}}$,
we obtain the query and video embeddings ($\mathbf{e}_{q},\mathbf{e}_{v})$ as
follows:

$\displaystyle\mathbf{e}_{q}$
$\displaystyle=f_{\text{enc}}(q)\in\mathbb{R}^{d_{q}}$
$\displaystyle\mathbf{e}_{v}$
$\displaystyle=f_{\text{enc}}(v)\in\mathbb{R}^{d_{v}},$

where $d_{q}$ and $d_{v}$ denote the dimension of query and video embeddings,
respectively. The goal of text-video retrieval is to search the most relevant
videos $\hat{v}$’s from a collection of videos $\mathcal{V}$ given a query
text $q$ as follows:

$\big{[}\hat{v}_{0},\dots,\hat{v}_{k-1}\big{]}=\textsc{top-k}_{v\in\mathcal{V}}\big{(}\textsc{sim}(\mathbf{e}_{q},\mathbf{e}_{v})\big{)},$
(1)

where $\textsc{sim}(\cdot)$ is a similarity function (e.g., cosine distance,
etc). Additionally, our system utilizes two key components: $\mathcal{M}$ and
$\mathcal{T}$. Here, $\mathcal{M}$ represents the LLMs and template function
$\mathcal{T}$ applies a pre-defined template to inputs333Note that
$\mathcal{M}$ is used interchangeably to indicate both a Large Language Model
(LLM) and a Multimodal Large Language Model (MLLM).,444Here, subscripts have
been omitted for simplicity. However, subscripts are employed in the equations
for each specific module (e.g., $\mathcal{M}_{\mathsf{question}}$). In
addition, the pre-defined template is presented in Appendix due to the limited
space.. Based on this background, we would like to introduce LLM-based
iterative navigation, involving multiple rounds of feedback learning and
reranking, leading to better performance and interpretability.

###  3.3 Question Generation

Suppose that we have retrieved candidates $\hat{v}^{r}_{k}$ where $r$ and $k$
indicate the round and the index of the retrieved top $K$ candidates,
respectively. We choose $\hat{v}^{r}_{0}$ as an anchor candidate and generate
the question with $\mathcal{M}_{\mathsf{question}}$ as follows555Note that we
use the caption from metadata of $\hat{v}^{r}_{0}$ and assume that each video
consists of $N$ frames.:

$\hat{q}^{r}=\mathcal{M}_{\mathsf{question}}\big{(}\mathcal{T}_{\mathsf{question}}(\hat{v}^{r}_{0})\big{)}$
(2)

Intuitively, top-ranked candidate is more likely to align with the user’s
query. This implies that assessing retrieved candidates with question
generated from $\hat{v}^{r}_{0}$ using LLMs would enhance retrieval
performance and interpretability.

###  3.4 Human-Simulating Agent

##### Video Question Answering.

Our underlying assumption is mitigating the discrepancy between user queries
and the information within the videos would be helpful for the better
retrieval performance. To this end, we answer the question $\hat{q}^{r}$ with
video $\hat{v}^{r}$ which consists of $N$ frames sampled per second as
follows:

$\big{[}\hat{a}^{(r,0)},\dots,\hat{a}^{(r,N)}\big{]}=\mathcal{M}_{\mathsf{answer}}\big{(}\mathcal{T}_{\mathsf{answer}}(\hat{q}^{r}),\hat{v}^{r}_{0}\big{)}$
(3)

It is worth noting that in a real-world scenario,
$\mathcal{M}_{\mathsf{answer}}$ could be replaced by a human to consider the
user perspective better. Additionally, using $N$ frames allows us to
efficiently handle the temporal information inherent to video, capturing the
dynamic aspects of the content. This approach enhances our ability to provide
a more comprehensive understanding and alignment with the user’s query.

##### Aggregation.

The individual generated answers for each frame
$\big{[}\hat{a}^{(r,0)},\dots,\hat{a}^{(r,N)}\big{]}$ are now subsequently fed
into an Aggregation Module which is designed to summarize the multiple frame-
level answers into a coherent and concise response to the original query as
follows:

$\tilde{a}^{r}=\mathcal{M}_{\mathsf{aggr}}\Big{(}\mathcal{T}_{\mathsf{aggr}}\big{(}[\hat{a}^{(r,0)},\dots,\hat{a}^{(r,N)}]\big{)}\Big{)}$
(4)

It is worth noting that Equation 3 provides answers for each frame, however,
the summarized answer should capture the importance of the video content. For
instance, if the question is “Did a cookie appear in the video?” and
individual answers for each frame are
$\big{[}\text{``No''},\text{``No''},\text{``Yes''},\text{``No''}\big{]}$, the
Aggregation Module will summarize and provide the final answer for the video
as “Yes”, since a cookie has appeared in the third frame. This process ensures
that the temporal and contextual information from all frames is considered,
resulting in a more accurate and relevant response.

###  3.5 Iterative Embedding Refinement for Reranking

Initially, we obtain the answer embedding $\mathbf{e}^{\tilde{a}^{r}}$ using
the multimodal encoder $f_{\text{enc}}$ as follows:
$\mathbf{e}^{\tilde{a}^{r}}=f_{\mathsf{enc}}(\tilde{a}^{r})$. Our objective is
to dynamically refine the embedding by combining the information from the
current round’s answer with the previous round’s refined embedding. To this
end, in the pursuit of refining embeddings iteratively to enhance retrieval
performance, we employ a spherical linear interpolation (SLERP) Shoemake
(1985), which is particularly appropriated for interpolating between
embeddings on the unit sphere, preserving the norm and the geometric
properties of the embeddings.

Given the embeddings $\mathbf{e}^{r-1}$ from the previous round and
$\mathbf{e}^{\tilde{a}^{r}}$, the angle $\theta$ between them is computed as:

$\theta=\arccos(\mathbf{e}^{\tilde{a}^{r}}\cdot\mathbf{e}^{r-1})$ (5)

Note that the angle is essential for determining the interpolation path.
Finally, the refined embedding for the current round $\mathbf{e}^{r}$ is then
calculated as:

$\mathbf{e}^{r}=\frac{\sin((1-\alpha)\theta)}{\sin(\theta)}\cdot\mathbf{e}^{\tilde{a}^{r}}+\frac{\sin(\alpha\theta)}{\sin(\theta)}\cdot\mathbf{e}^{r-1},$
(6)

where $\alpha\in[0,1]$ is a hyperparameter that balances the influence of the
current answer embedding and the previous refined embedding. This
interpolation not only ensures a smooth transition across embedding spaces but
also incorporates both the originality of the current response and the
semantic context retained from prior interactions. We assume that the
potential risk of the iterative embedding refinement is query drift Mitra et
al. (1998); Zighelnic and Kurland (2008); Shtok et al. (2012), a common
phenomenon in information retrieval where the focus inadvertently shifts away
from the original query intent due to the inclusion of progressively
accumulated details. To mitigate the potential risk, we set the $\alpha=0.8$,
prioritizing the query and earlier answer embeddings over the most recent
answers. We expect that this simple yet effective strategy would preserve the
thematic integrity of the initial query, akin to human conversational patterns
where early-mentioned topics typically set the context for the entire
conversation.

Model | Rounds | MSR-VTT | MSVD | ActivityNet
---|---|---|---|---
R@1 | R@5 | R@10 | R@1 | R@5 | R@10 | R@1 | R@5 | R@10
VAST Chen et al. (2024a) | - | 49.30 | 68.30 | 73.90 | - | - | - | - | - | -
InternVideo2-6B Wang et al. (2024b) | - | 55.9 | 78.3 | 85.1 | 59.3 | 84.4 | 89.6 | 63.2 | 85.6 | 92.5
LanguageBind-H Zhu et al. (2023) | - | 44.8 | 70.0 | 78.7 | 53.9 | 80.4 | 87.8 | 41.0 | 68.4 | 80.8
VideoPrism-g Madan et al. (2024) | - | 39.7 | 63.7 | - | - | - | - | 52.7 | 79.4 | -
Marengo-2.6 Labs (2024) | - | 49.35 | 73.47 | - | - | - | - | 55.36 | 82.55 | -
MERLIN | 0 | 44.40 | 67.60 | 76.20 | 52.39 | 77.16 | 84.78 | 56.58 | 84.77 | 91.73
1 | 56.40 | 80.00 | 87.00 | 61.94 | 85.97 | 91.79 | 59.96 | 89.01 | 93.91
2 | 66.40 | 86.00 | 92.80 | 67.61 | 90.45 | 94.63 | 62.68 | 90.42 | 94.34
3 | 72.60 | 91.80 | 95.60 | 71.79 | 91.79 | 96.87 | 66.05 | 90.97 | 95.54
4 | 76.20 | 93.40 | 97.00 | 74.78 | 93.28 | 96.87 | 67.14 | 91.08 | 95.54
5 | 78.00 | 94.20 | 96.80 | 77.61 | 94.48 | 97.31 | 68.44 | 91.95 | 96.63

Table 1: The performance of zero-shot text-video retrieval on MSR-VTT, MSVD,
and ActivityNet.

##  4 Experimental Results

###  4.1 Setting

To utilize mutlimodal encoders and LLMs without needing private GPUs, we use
Google Multimodal Embedding API666https://cloud.google.com/generative-ai-
studio for encoding video and text, and the OpenAI GPT-4o API Achiam et al.
(2023)777https://chat.openai.com/ for generating questions and answers. These
APIs offers comparable performance and reproducibility on benchmarks without
private GPUs.

We evaluate MERLIN across three datasets: MSR-VTT, MSVD, and ActivityNet. For
MSR-VTT, we sampled 500 videos from its 1,000-sample validation split. From
MSVD and ActivityNet, we sampled all 670 and 919 videos from their respective
test sets. For videos with multiple captions, we randomly selected one query
per video.

###  4.2 Performance on Text-Video Retrieval

The performance of our system is presented in Table 1, demonstrating its
efficacy through multiple rounds of feedback learning, reflecting the system’s
ability to iteratively to refine and incorporate feedback. Particularly,
MERLIN shows significant improvements with each round of feedback: On the MSR-
VTT dataset, MERLIN shows improvements from a R@1 of $44.40$ to $78.00$, on
the MSVD from $52.39$ to $77.61$, and on ActivityNet from $56.58$ to $68.44$
by the final round.

This highlights MERLIN’s capacity to adapt and enhance its response through
iterative feedback learning. Despite the distinct challenges posed by each
dataset, MERLIN significantly boosts its performance, thereby affirming the
effectiveness of leveraging iterative feedback learning to enhance text-video
retrieval task.

###  4.3 Average Ranking of QA Rounds

Figure 4: An illustration of the average ranking of target video for each
dataset.

In addition to the retrieval performance presented in Table 1, the
effectiveness of the iterative query enrichment is further highlighted by
examining the average ranking of the target videos across question-answer
rounds. This analysis is helpful for understanding how the process enhances
the ranking of the target videos. As illustrated Figure 4, the average ranking
of the target video consistently improves each consecutive round across all
datasets. For instance, on the MSR-VTT dataset, the average ranking
significantly improves from $18.57$ in round $0$ to $2.5$ by final round.
Similar improvements are observed on other datasets, with the average ranking
on MSVD improving from $13.84$ to $2.4$, and on ActivityNet from $6$ to $2.6$.
This demonstrates the consistent improvement, thereby confirming the
effectiveness of MERLIN in reranking through iterative feedback learning.

###  4.4 The Effect of $\alpha$ in Iterative Embedding Refinement

As mentioned in Section 3.5, our assumption is mitigating query drift would
preserve the thematic integrity of the initial query by assigning high
$\alpha$ value, prioritizing the query and earlier answer embeddings over the
most recent answers.

To validate our assumption in contrast to the experiment’s higher
$\alpha=0.8$, we conduct additional experiments with assigning a reduced value
$\alpha=0.2$, which allows us to observe the impact of shifting emphasis
towards the latest answers. The results on the MSR-VTT and MSVD datasets show
that setting a lower $\alpha$ initially improves retrieval performance in
early rounds but leads to a decline after a few rounds, indicating potential
query drift. Furthermore, the average ranking of the target video deteriorates
in later rounds, suggesting the query representation has deviated from the
user’s original intent.

Specifically, for MSR-VTT, MERLIN got 44.4/67.60/76.20 for recall@1/5/10 at
round $0$ respectively but ended up with 61.6/81.20/87.00 respectively at
round $5$. For MSVD, MERLIN got 52.39/77.16/84.78 for recall@1/5/10 at round
$0$ respectively but ended up with 56.87/78.51/84.63 respectively at round
$5$.

##  5 Conclusion

In conclusion, the MERLIN framework addresses a critical gap in the field of
text-video retrieval by integrating the often-overlooked user perspective into
the retrieval process. This integration is achieved through a novel, training-
free pipeline that utilizes LLMs for iterative feedback learning, allowing for
the dynamic refinement of query embeddings based on user interactions. MERLIN
not only aligns more closely with user intent but also enhances the overall
search experience by reducing discrepancies between user queries and retrieved
video content.

The implementation of MERLIN shows a significant advancement in multimedia
retrieval, introducing the first retrieval-rerank pipeline in this domain. By
incorporating iterative feedback mechanisms inspired by human cognitive
processes, MERLIN facilitates a more aligned and context-aware approach to
text-video retrieval. Our experimental results demonstrate the effectiveness
of this approach, with substantial improvements in retrieval performance
observed across MSR-VTT, MSVD, and ActivityNet datasets.

## Limitations

While our results are promising, we acknowledge that we cannot provide a
comprehensive guide for adapting MERLIN to different settings, as we have not
extensively explored the impact of changing various components. However, the
core principle of integrating user feedback to iteratively refine the query
embedding appears to be a robust approach, regardless of pipeline components,
the specific domain or data modality. Future work could investigate the
generalization of MERLIN to other multimedia retrieval tasks and explore the
optimal configurations for different scenarios.

Other limitation of our approach lies in the use of a human-simulating LLM
agent for answering questions based on static video frames. While this agent
aims to mimic the human feedback process, it lacks the capability to grasp
temporal information and attributes that require a high-level understanding of
motion and dynamics. Since the LLM agent first generates answers based on
static images and then aggregates them, it struggles to capture knowledge
about direction, speed, and other temporal aspects present in the videos.

Moreover, as most pre-trained video encoders also have shortcomings in
effectively modeling temporal capabilities Liu et al. (2024), our video
encoder may be affected by this limitation as well. This creates a kind of
chicken-and-egg problem, where video encoders can benefit from temporal-rich
information only when they can understand temporal information effectively.
Conversely, even if the video question-answering module (or similar
counterparts) can handle temporal-rich information, if the video encoder does
not possess the same capability, it may not benefit from this information.
This temporal modeling challenge is a prevalent issue that the community needs
to address collectively.

## Acknowledgements

This work was partially supported by Deep Learning Research Group AttentionX.

## References

  * Achiam et al. (2023) Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. 2023.  Gpt-4 technical report.  _arXiv preprint arXiv:2303.08774_.
  * Akyürek et al. (2023) Afra Feyza Akyürek, Ekin Akyürek, Aman Madaan, Ashwin Kalyan, Peter Clark, Derry Wijaya, and Niket Tandon. 2023.  Rl4f: Generating natural language feedback with reinforcement learning for repairing model outputs.  _arXiv preprint arXiv:2305.08844_.
  * Anne Hendricks et al. (2017) Lisa Anne Hendricks, Oliver Wang, Eli Shechtman, Josef Sivic, Trevor Darrell, and Bryan Russell. 2017.  Localizing moments in video with natural language.  In _Proceedings of the IEEE international conference on computer vision_ , pages 5803–5812.
  * Böhm et al. (2019) Florian Böhm, Yang Gao, Christian M. Meyer, Ori Shapira, Ido Dagan, and Iryna Gurevych. 2019.  Better rewards yield better summaries: Learning to summarise without references.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 3110–3120, Hong Kong, China. Association for Computational Linguistics.
  * Caba Heilbron et al. (2015) Fabian Caba Heilbron, Victor Escorcia, Bernard Ghanem, and Juan Carlos Niebles. 2015.  Activitynet: A large-scale video benchmark for human activity understanding.  In _Proceedings of the ieee conference on computer vision and pattern recognition_ , pages 961–970.
  * Chen and Dolan (2011) David L. Chen and William B. Dolan. 2011.  Collecting highly parallel data for paraphrase evaluation.  In _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics (ACL-2011)_ , Portland, OR.
  * Chen et al. (2024a) Sihan Chen, Handong Li, Qunbo Wang, Zijia Zhao, Mingzhen Sun, Xinxin Zhu, and Jing Liu. 2024a.  Vast: A vision-audio-subtitle-text omni-modality foundation model and dataset.  _Advances in Neural Information Processing Systems_ , 36.
  * Chen et al. (2024b) Tsai-Shien Chen, Aliaksandr Siarohin, Willi Menapace, Ekaterina Deyneka, Hsiang-wei Chao, Byung Eun Jeon, Yuwei Fang, Hsin-Ying Lee, Jian Ren, Ming-Hsuan Yang, and Sergey Tulyakov. 2024b.  Panda-70m: Captioning 70m videos with multiple cross-modality teachers.  _CoRR_ , abs/2402.19479.
  * Chen et al. (2023) Zhe Chen, Jiannan Wu, Wenhai Wang, Weijie Su, Guo Chen, Sen Xing, Muyan Zhong, Qinglong Zhang, Xizhou Zhu, Lewei Lu, Bin Li, Ping Luo, Tong Lu, Yu Qiao, and Jifeng Dai. 2023.  Internvl: Scaling up vision foundation models and aligning for generic visual-linguistic tasks.  _CoRR_ , abs/2312.14238.
  * Doherty and Balzer (1988) Michael E. Doherty and William K. Balzer. 1988.  Chapter 5 cognitive feedback.  In Berndt Brehmer and C.R.B. Joyce, editors, _Human Judgment the SJT View_ , volume 54 of _Advances in Psychology_ , pages 163–197. North-Holland.
  * Fang et al. (2023) Bo Fang, Wenhao Wu, Chang Liu, Yu Zhou, Yuxin Song, Weiping Wang, Xiangbo Shu, Xiangyang Ji, and Jingdong Wang. 2023.  UATVR: uncertainty-adaptive text-video retrieval.  In _IEEE/CVF International Conference on Computer Vision, ICCV 2023, Paris, France, October 1-6, 2023_ , pages 13677–13687. IEEE.
  * Flower and Hayes (1981) Linda Flower and John R. Hayes. 1981.  A cognitive process theory of writing.  _College Composition and Communication_ , 32(4):365–387.
  * Glaese et al. (2022) Amelia Glaese, Nat McAleese, Maja Trębacz, John Aslanides, Vlad Firoiu, Timo Ewalds, Maribeth Rauh, Laura Weidinger, Martin Chadwick, Phoebe Thacker, et al. 2022.  Improving alignment of dialogue agents via targeted human judgements.  _arXiv preprint arXiv:2209.14375_.
  * Hao and Zhang (2023) Xiaoshuai Hao and Wanqian Zhang. 2023.  Uncertainty-aware alignment network for cross-domain video-text retrieval.  In _Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023_.
  * Hao et al. (2023) Xiaoshuai Hao, Wanqian Zhang, Dayan Wu, Fei Zhu, and Bo Li. 2023.  Dual alignment unsupervised domain adaptation for video-text retrieval.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2023, Vancouver, BC, Canada, June 17-24, 2023_ , pages 18962–18972. IEEE.
  * Huang et al. (2023) Siteng Huang, Biao Gong, Yulin Pan, Jianwen Jiang, Yiliang Lv, Yuyuan Li, and Donglin Wang. 2023.  Vop: Text-video co-operative prompt tuning for cross-modal retrieval.  In _IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2023, Vancouver, BC, Canada, June 17-24, 2023_ , pages 6565–6574. IEEE.
  * Jang et al. (2024) Young Kyun Jang, Dat Huynh, Ashish Shah, Wen-Kai Chen, and Ser-Nam Lim. 2024.  Spherical linear interpolation and text-anchoring for zero-shot composed image retrieval.  _arXiv preprint arXiv:2405.00571_.
  * Jin et al. (2023) Peng Jin, Hao Li, Zesen Cheng, Jinfa Huang, Zhennan Wang, Li Yuan, Chang Liu, and Jie Chen. 2023.  Text-video retrieval with disentangled conceptualization and set-to-set alignment.  In _Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI 2023, 19th-25th August 2023, Macao, SAR, China_ , pages 938–946. ijcai.org.
  * Labs (2024) Twelve Labs. 2024.  Introducing marengo-2.6-medium.
  * Lee et al. (2024) Dongyub Lee, Eunhwan Park, Hodong Lee, and Heuiseok Lim. 2024.  Ask, assess, and refine: Rectifying factual consistency and hallucination in LLMs with metric-guided feedback learning.  In _Proceedings of the 18th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2422–2433, St. Julian’s, Malta. Association for Computational Linguistics.
  * Lester et al. (2021) Brian Lester, Rami Al-Rfou, and Noah Constant. 2021.  The power of scale for parameter-efficient prompt tuning.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 3045–3059, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Levy et al. (2023) Matan Levy, Rami Ben-Ari, Nir Darshan, and Dani Lischinski. 2023.  Chatting makes perfect: Chat-based image retrieval.  In _Advances in Neural Information Processing Systems_ , volume 36, pages 61437–61449. Curran Associates, Inc.
  * Liang et al. (2024) Youwei Liang, Junfeng He, Gang Li, Peizhao Li, Arseniy Klimovskiy, Nicholas Carolan, Jiao Sun, Jordi Pont-Tuset, Sarah Young, Feng Yang, Junjie Ke, Krishnamurthy Dj Dvijotham, Katherine M. Collins, Yiwen Luo, Yang Li, Kai J Kohlhoff, Deepak Ramachandran, and Vidhya Navalpakkam. 2024.  Rich human feedback for text-to-image generation.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 19401–19411.
  * Liu et al. (2024) Yuanxin Liu, Shicheng Li, Yi Liu, Yuxiang Wang, Shuhuai Ren, Lei Li, Sishuo Chen, Xu Sun, and Lu Hou. 2024.  Tempcompass: Do video llms really understand videos?  _arXiv preprint arXiv:2403.00476_.
  * Liu et al. (2021) Zheyuan Liu, Cristian Rodriguez-Opazo, Damien Teney, and Stephen Gould. 2021.  Image retrieval on real-life images with pre-trained vision-and-language models.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , pages 2125–2134.
  * Madaan et al. (2023) Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, Sean Welleck, Bodhisattwa Prasad Majumder, Shashank Gupta, Amir Yazdanbakhsh, and Peter Clark. 2023.  Self-refine: Iterative refinement with self-feedback.  _CoRR_ , abs/2303.17651.
  * Madan et al. (2024) Neelu Madan, Andreas Moegelmose, Rajat Modi, Yogesh S Rawat, and Thomas B Moeslund. 2024.  Foundation models for video understanding: A survey.  _arXiv preprint arXiv:2405.03770_.
  * Mitra et al. (1998) Mandar Mitra, Amit Singhal, and Chris Buckley. 1998.  Improving automatic query expansion.  In _Proceedings of the 21st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’98, page 206–214, New York, NY, USA. Association for Computing Machinery.
  * Ouyang et al. (2022) Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022.  Training language models to follow instructions with human feedback.  _Advances in Neural Information Processing Systems_ , 35:27730–27744.
  * Shoemake (1985) Ken Shoemake. 1985.  Animating rotation with quaternion curves.  In _Proceedings of the 12th Annual Conference on Computer Graphics and Interactive Techniques, SIGGRAPH 1985, San Francisco, California, USA, July 22-26, 1985_ , pages 245–254. ACM.
  * Shtok et al. (2012) Anna Shtok, Oren Kurland, David Carmel, Fiana Raiber, and Gad Markovits. 2012.  Predicting query performance by query-drift estimation.  _ACM Trans. Inf. Syst._ , 30(2).
  * Stiennon et al. (2020) Nisan Stiennon, Long Ouyang, Jeff Wu, Daniel M. Ziegler, Ryan J. Lowe, Chelsea Voss, Alec Radford, Dario Amodei, and Paul Christiano. 2020.  Learning to summarize from human feedback.  _ArXiv_ , abs/2009.01325.
  * Wang et al. (2024a) Yi Wang, Kunchang Li, Xinhao Li, Jiashuo Yu, Yinan He, Guo Chen, Baoqi Pei, Rongkun Zheng, Jilan Xu, Zun Wang, Yansong Shi, Tianxiang Jiang, Songze Li, Hongjie Zhang, Yifei Huang, Yu Qiao, Yali Wang, and Limin Wang. 2024a.  Internvideo2: Scaling video foundation models for multimodal video understanding.  _CoRR_ , abs/2403.15377.
  * Wang et al. (2024b) Yi Wang, Kunchang Li, Xinhao Li, Jiashuo Yu, Yinan He, Guo Chen, Baoqi Pei, Rongkun Zheng, Jilan Xu, Zun Wang, et al. 2024b.  Internvideo2: Scaling video foundation models for multimodal video understanding.  _arXiv preprint arXiv:2403.15377_.
  * Wang et al. (2023) Ziyang Wang, Yi-Lin Sung, Feng Cheng, Gedas Bertasius, and Mohit Bansal. 2023.  Unified coarse-to-fine alignment for video-text retrieval.  In _IEEE/CVF International Conference on Computer Vision, ICCV 2023, Paris, France, October 1-6, 2023_ , pages 2804–2815. IEEE.
  * Wu et al. (2020) Jeff Wu, Long Ouyang, Daniel M Ziegler, Nisan Stiennon, Ryan Lowe, Jan Leike, and Paul Christiano. 2020.  Recursively summarizing books with human feedback.  In _Advances in Neural Information Processing Systems_.
  * Wu et al. (2023) Wenhao Wu, Haipeng Luo, Bo Fang, Jingdong Wang, and Wanli Ouyang. 2023.  Cap4video: What can auxiliary captions do for text-video retrieval? In _IEEE/CVF Conference on Computer Vision and Pattern Recognition, CVPR 2023, Vancouver, BC, Canada, June 17-24, 2023_ , pages 10704–10713. IEEE.
  * Xu et al. (2016) Jun Xu, Tao Mei, Ting Yao, and Yong Rui. 2016.  Msr-vtt: A large video description dataset for bridging video and language.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 5288–5296.
  * Zhao et al. (2024) Yue Zhao, Long Zhao, Xingyi Zhou, Jialin Wu, Chun-Te Chu, Hui Miao, Florian Schroff, Hartwig Adam, Ting Liu, Boqing Gong, Philipp Krähenbühl, and Liangzhe Yuan. 2024.  Distilling vision-language models on millions of videos.  _CoRR_ , abs/2401.06129.
  * Zhu et al. (2023) Bin Zhu, Bin Lin, Munan Ning, Yang Yan, Jiaxi Cui, HongFa Wang, Yatian Pang, Wenhao Jiang, Junwu Zhang, Zongwei Li, et al. 2023.  Languagebind: Extending video-language pretraining to n-modality by language-based semantic alignment.  _arXiv preprint arXiv:2310.01852_.
  * Ziegler et al. (2019) Daniel M Ziegler, Nisan Stiennon, Jeffrey Wu, Tom B Brown, Alec Radford, Dario Amodei, Paul Christiano, and Geoffrey Irving. 2019.  Fine-tuning language models from human preferences.  _arXiv preprint arXiv:1909.08593_.
  * Zighelnic and Kurland (2008) Liron Zighelnic and Oren Kurland. 2008.  Query-drift prevention for robust query expansion.  In _Proceedings of the 31st Annual International ACM SIGIR Conference on Research and Development in Information Retrieval_ , SIGIR ’08, page 825–826, New York, NY, USA. Association for Computing Machinery.

##  Appendix A Algorithm

Algorithm 1 Iterative video reranking with question answering rounds

1:encoder $f_{\text{enc}}()$, user query $q\in\mathcal{Q}$, video
$v\in\mathcal{V}$, total question-answer round $R$, retrieved top-$k$ videos
at round $r$ $\hat{v}^{r}$, $i$-th candidate among top-$k$ videos at round $r$
$\hat{v}^{r}_{i}$

2:Encode $\mathbf{e}_{q}=f_{\text{enc}}(q)$ given user query $q$

3:Encode $\mathbf{e}_{v}=f_{\text{enc}}(v)$ given video $v$

4:Retrieve
$\hat{v}^{0}=\textsc{top-k}_{v\in\mathcal{V}}\big{(}\textsc{sim}(\mathbf{e}_{q},\mathbf{e}_{v})\big{)}$
(Equation 1)

5:Initialize message list $m=[]$

6:for $r=1$ to $R$ do

7: Append metadata of $\hat{v}^{r-1}_{0}$ to $m$

8: Generate question $\hat{q}^{r}=\mathcal{M}_{\mathsf{question}}(m)$
(Equation 2)

9: Append $\hat{q}^{r}$ to $m$

10: Generate frame-level answers
$\big{[}\hat{a}^{(r,0)},\dots,\hat{a}^{(r,N)}\big{]}=\mathcal{M}_{\mathsf{answer}}(\hat{q}^{r}:\text{video
in mind})$ (Equation 3)

11: Aggregate frame-level answers
$\tilde{a}^{r}=\mathcal{M}_{\mathsf{aggr}}([\hat{a}^{(r,0)},\dots,\hat{a}^{(r,N)}\big{]})$
(Equation 4)

12: Encode $\mathbf{e}_{A^{r}}=f_{\text{enc}}(A^{r})$

13: Refine embedding $e=Refine(e_{q},\cdots,e_{A^{r}})$

14: Retrieve
$\hat{v}^{r}=\textsc{top-k}_{v\in\mathcal{V}}\big{(}\textsc{sim}(\mathbf{e},\mathbf{e}_{v})\big{)}$
(Equation 1)

15:end for

16:return Reranked retrieved videos $\hat{v}^{r}_{k}$

##  Appendix B Prompt Template

###  B.1 Prompt for Question Generation Module

In order to get useful information from user, it is critical to ask good
question that could draw user intention. As depicted in Table 2, we set top
$1$ ranked video as anchor video and prompted GPT-4o to refer to anchor
video’s metadata. In our case, we used the video’s caption as metadata.
However, we believe that questions could be more diverse if we could use other
data such as Automatic Speech Recognition (ASR) captions, the characteristics
of the video, and so on. As MERLIN proceeds with the chat with the user (a
user-simulating agent), we stacked previous questions and answers and To
encourage GPT-4 to generate diverse questions without repeating previous
ones..

###  B.2 Prompts for Human-Simulating Agent

As human-simulating agent has two steps for answering to the question
regarding “video in mind”, we have two different settings for each step. This
method lacks in understanding direction, speed and other temporal knowledge as
we dealt in the Limitation. However, we experimentally showed that our human-
simulating agent is helpful in enriching information.

####  B.2.1 Prompt for Question-Answering Module

As depicted in Table 3, we sampled frame from video for every 1 second. Then
we asynchronously inputed sampled frame and question from MERLIN. We prompted
GPT-4o to answer in detail about fact and not just answer in “Yes” or “No”.
However this question-answering module is the part that takes up large portion
of API cost so video may be sample in wider stride to lower the API cost.

####  B.2.2 Prompt for Aggregation Module

As depicted in Table 4, we aggregate all the answers generated from the
question-answering module. We prompted GPT-4o to aggregate multiple answers
made with multiple frame at question-answering module and appended an
aggregating example.

##  Appendix C Case Studies

The main objective of MERLIN is to improve the ranking of failure cases where
the target video is not among the top-ranked candidates. At the same time, it
is important to keep the success case to stay in the top-ranked candidates
while MERLIN proceeds chatting with user. Retrieving the target video among
the top-ranked candidates indicates that MERLIN consistently reflects user
intention during the conversation. To qualitatively verify that MERLIN
performs its tasks according to the aforementioned objectives, we reviewed
several case studies. We focused on how MERLIN bring the rank of failure
cases.

###  C.1 Case study for ActivityNet

As shown in the Figure 5, initial ranking of target video was $224$ using
paired query from dataset. However as MERLIN augmented query using user’s
response, rank boosted to $36\rightarrow 14\rightarrow 4\rightarrow 1$ as
round proceeds. During the conversation, MERLIN was able to understand that
the user was looking for a video about Christmas themes, featuring two people,
and involving gift wrapping. It managed to rank the target video on top with
augmented information.

###  C.2 Case study for MSVD

As shown in Figure 6, initial ranking of target video was $154$ using paired
query from dataset. However as MERLIN augmented query using user’s response,
rank boosted to $14\rightarrow 1\rightarrow 1\rightarrow 1$ as round proceeds.
During the conversation, MERLIN was able to understand that the user was
looking for a video about NBA All-Star game, broadcasted on TNT and score
board telling 74:75. It managed to rank the target video on top with augmented
information at early round and manage to keep top rank during multiple rounds.

###  C.3 Case study for MSR-VTT

As shown in Figure 7, initial ranking of target video was $361$ using paired
query from dataset. However as MERLIN augmented query using user’s response,
rank boosted to $197\rightarrow 14\rightarrow 1\rightarrow 1$ as round
proceeds. During the conversation, MERLIN was able to understand that the
detailed feature and gesture of human featured on “video in mind”. It managed
to rank the target video on top with augmented information at early round and
manage to keep top rank during multiple rounds.

Details about question generation module in MERLIN
---
System prompt
You are given caption about certain video(anchor video) and query used to
retrieve the anchor video. However this video may not be the exact video the I
am looking for.
Your role is to ask question about the video I have in mind to get more
information about video. You have 5 rounds and you can only ask one question
at a time.
Focus on attributes like number of people, color, shape and etc.
Initial prompt
This is caption of retrieved video. Read the video captions and ask some
question to gain more information to help find out exact video. Some video may
not have caption due to API error saying sorry I can’t provide blah blah.
Captions for video: {anchor video’s caption}
Question:
Question-answering round prompt
answer: {Aggregated answer from user-simulating Agent}
Based on answer, here’s caption of reranked video.
caption: {reranked top1 video caption as anchor caption}
Keep asking.
Question:
Max tokens
\- 1500
Temperature
\- 0.75
Table 2:  The instruction and specification for question generation module in
MERLIN using GPT-4o. After initial retrieval at round $0$, MERLIN generates
question with initial prompt using information of anchor video’s caption.
After user answers to the question, MERLIN rerank the and generate question
using new anchor and question-answering round prompt.  Details about human-
simulating agent (question-answering module)
---
System Prompt
You are a helpful assistant that answer the question with details. Don’t jsut
answer in yes or no. Provide more details(about facts) about the image that
might help the questioner.
Input format
\- text: {Question from MERLIN}
\- image: {Image encoded in base64 captured from video in mind in 1 second
interval.}
Max tokens
\- 50
Temperature
\- 0.3
Image sampling rate
\- 1 second
Table 3:  The instruction and specification for video question-answering
human-simulating agent using GPT-4o (question-answering module).  Details
about human-simulating agent (aggregation module)
---
System Prompt
The VQA model is designed to answer questions based on images. To apply it to
videos, frames are uniformly extracted from the video over time, and the model
provides an answer for each frame to a given question. This means that for a
single question, there will be multiple answers - one for each extracted
frame. Your role is to review all of the individual answers and summarize them
to provide a final answer to the original question. When making final answer,
don’t user unnecessary words like ‘Based on the individual answers provided by
the VQA model,’. Just answer to the question.
For example, if the question is “Did a cookie appear in the video?” and the
individual answers from the frames are [“No”, “No”, “Yes”, “No”], then since a
cookie appeared in the 3rd frame, you should summarize and answer the question
as “Yes”. Length of aggregated answer should be around 30~35 words.
Input format
Question: {Question from MERLIN}
VQA Answer: {Answers from question-answering module}
Aggregated Answer:
Max tokens
\- 100
Temperature
\- 0.5
Table 4:  The instruction and specification for video question-answering
human-simulating agent using GPT-4o (aggregation module).  Figure 5:
Qualitative evaluation of MERLIN on ActivityNet. sample: v_juiMCvZUYwk. Figure
6: Qualitative evaluation of MERLIN on MSVD. sample: hbE29pZh76I_3_8. Figure
7: Qualitative evaluation of MERLIN on MSR-VTT1ka. sample: video8471.


* Rashid et al. [2021] Mamunur Rashid, Bifta Sama Bari, Yusri Yusup, Mohamad Anuar Kamaruddin, and Nuzhat Khan.  A Comprehensive Review of Crop Yield Prediction Using Machine Learning Approaches With Special Emphasis on Palm Oil Yield Prediction.  _IEEE Access_ , 9:63406–63439, 2021.  ISSN 2169-3536.  doi:10.1109/ACCESS.2021.3075159.  URL https://ieeexplore.ieee.org/document/9410627/.
  * Van Klompenburg et al. [2020] Thomas Van Klompenburg, Ayalew Kassahun, and Cagatay Catal.  Crop yield prediction using machine learning: A systematic literature review.  _Computers and Electronics in Agriculture_ , 177:105709, 2020.
  * Bali and Singla [2022] Nishu Bali and Anshu Singla.  Emerging Trends in Machine Learning to Predict Crop Yield and Study Its Influential Factors: A Survey.  _Archives of Computational Methods in Engineering_ , 29(1):95–112, January 2022.  ISSN 1134-3060, 1886-1784.  doi:10.1007/s11831-021-09569-8.  URL https://link.springer.com/10.1007/s11831-021-09569-8.
  * Woittiez et al. [2017] Lotte S Woittiez, Mark T Van Wijk, Maja Slingerland, Meine Van Noordwijk, and Ken E Giller.  Yield gaps in oil palm: A quantitative review of contributing factors.  _European Journal of Agronomy_ , 83:57–77, 2017.
  * Ahansal et al. [2022] Youssef Ahansal, Mourad Bouziani, Reda Yaagoubi, Imane Sebari, Karima Sebari, and Lahcen Kenny.  Towards smart irrigation: A literature review on the use of geospatial technologies and machine learning in the management of water resources in arboriculture.  _Agronomy_ , 12(2):297, 2022.
  * Abioye et al. [2022] Emmanuel Abiodun Abioye, Oliver Hensel, Travis J Esau, Olakunle Elijah, Mohamad Shukri Zainal Abidin, Ajibade Sylvester Ayobami, Omosun Yerima, and Abozar Nasirahmadi.  Precision irrigation management using machine learning and digital farming solutions.  _AgriEngineering_ , 4(1):70–103, 2022.
  * Saleem et al. [2021] Muhammad Hammad Saleem, Johan Potgieter, and Khalid Mahmood Arif.  Automation in agriculture by machine and deep learning techniques: A review of recent developments.  _Precision Agriculture_ , 22:2053–2091, 2021.
  * Christias and Mocanu [2021] Panagiotis Christias and Mariana Mocanu.  A machine learning framework for olive farms profit prediction.  _Water_ , 13(23):3461, 2021.
  * Islam et al. [2021] Nahina Islam, Md Mamunur Rashid, Faezeh Pasandideh, Biplob Ray, Steven Moore, and Rajan Kadel.  A review of applications and communication technologies for internet of things (iot) and unmanned aerial vehicle (uav) based sustainable smart farming.  _Sustainability_ , 13(4):1821, 2021.
  * Vianny et al. [2022] D Maria Manuel Vianny, A John, Senthil Kumar Mohan, Aliza Sarlan, Ali Ahmadian, et al.  Water optimization technique for precision irrigation system using iot and machine learning.  _Sustainable Energy Technologies and Assessments_ , 52:102307, 2022.
  * Truong et al. [2021] Viet-Hung Truong, Quang Viet Ly, Van-Chin Le, Trong-Bang Vu, Tuan-Thach Tran, Peter Goethals, et al.  Machine learning-based method for forecasting water levels in irrigation and drainage systems.  _Environmental Technology & Innovation_, 23:101762, 2021\.
  * Bhoi et al. [2021] Ashutosh Bhoi, Rajendra Prasad Nayak, Sourav Kumar Bhoi, and Srinivas Sethi.  Automated precision irrigation system using machine learning and iot.  In _Intelligent Systems: Proceedings of ICMIB 2020_ , pages 275–282. Springer, 2021.
  * Sinha and Dhanalakshmi [2022] Bam Bahadur Sinha and R. Dhanalakshmi.  Recent advancements and challenges of Internet of Things in smart agriculture: A survey.  _Future Generation Computer Systems_ , 126:169–184, 2022\.  Publisher: Elsevier.
  * Fahad et al. [2023] Shah Fahad, Fang Su, Sufyan Ullah Khan, Muhammad Rashid Naeem, and Kailei Wei.  Implementing a novel deep learning technique for rainfall forecasting via climatic variables: An approach via hierarchical clustering analysis.  _Science of The Total Environment_ , 854:158760, 2023.  ISSN 0048-9697.  Publisher: Elsevier.
  * Kundu et al. [2021] Nidhi Kundu, Geeta Rani, Vijaypal Singh Dhaka, Kalpit Gupta, Siddaiah Chandra Nayak, Sahil Verma, Muhammad Fazal Ijaz, and Marcin Woźniak.  Iot and interpretable machine learning based framework for disease prediction in pearl millet.  _Sensors_ , 21(16):5386, 2021.
  * Martos et al. [2021] Vanesa Martos, Ali Ahmad, Pedro Cartujo, and Javier Ordoñez.  Ensuring agricultural sustainability through remote sensing in the era of agriculture 5.0.  _Applied Sciences_ , 11(13):5911, 2021.


# Optimal quantum simulation of open quantum systems

Pragati Gupta<EMAIL_ADDRESS>Indian Institute of Science, C.V. Raman
Avenue, Bengaluru 560012, India  C. M. Chandrashekar<EMAIL_ADDRESS>The
Institute of Mathematical Sciences, C. I. T. Campus, Taramani, Chennai 600113,
India  Homi Bhabha National Institute, Training School Complex, Anushakti
Nagar, Mumbai 400094, India  Dept. of Instrumentation & Applied Physics,
Indian Institute of Sciences, C.V. Raman Avenue, Bengaluru 560012, India

###### Abstract

Digital quantum simulation on quantum systems require algorithms that can be
implemented using finite quantum resources. Recent studies have demonstrated
digital quantum simulation of open quantum systems on Noisy Intermediate-Scale
Quantum (NISQ) devices. In this work, we develop quantum circuits for optimal
simulation of Markovian and Non-Markovian open quantum systems. The circuits
use ancilla qubits to simulate the environment, and memory effects are induced
by storing information about the system on extra qubits. We simulate the
amplitude damping channel and dephasing channel as examples of the framework
and infer (Non-)Markovianity from the (non-)monotonic behaviour of the
dynamics. Further, we develop a method to optimize simulations by decomposing
complex open quantum dynamics into smaller parts, that can be simulated using
a small number of qubits. We show that this optimization reduces quantum space
complexity from $O(l)$ to $O(1)$ for simulating the environment.

##  I Introduction

Real world quantum systems interact with the environment as opposed to the
idealized notion of closed quantum systems. The theory of open quantum systems
breuer2002theory ; rivas2012open  provides a useful framework to study a
variety of phenomena, such as the decoherence in quantum systems
opendecoherence , out of equilibrium many-body dynamics manybody , quantum
field theory qft  and has applications to studying information processing in
the physical systems. A description of open quantum systems in the form of
partial differential equation of motion is provided by the quantum master
equations. These equations are derived under certain assumptions about the
dynamics and a general form of the master equation for an open quantum system
is not known. For example, the Lindblad master equation lindblad , holds under
the Born-Markov approximation and can not be used to describe Non-Markovian
systems. Another formulation, the Kraus representation book  provides a more
general framework and has been widely used to characterize open quantum
systems. Quantum simulation of open quantum systems can provide insights into
system-environment interactions, that can be used to understand and control
noisy physical systems johansson2012qutip .

Quantum simulators are devices that can turn the exponential scaling of
resources needed to simulate quantum systems using classical systems into a
favourable polynomial overhead. Ongoing experimental research is geared
towards making quantum simulators with small number of qubits, called Noisy
Intermediate Scale Quantum (NISQ) devices as first practical applications of a
quantum computer nisq ; nearterm . Quantum simulation of open quantum systems
usually relies on using a simulator that directly mimics the dynamics of the
quantum system under interest. This approach is useful in near term analog
quantum simulations and has been applied to a number of systems analog2 ;
analog3 ; analog4 ; mostame2017emulation ; mostame2012quantum . In contrast, a
universal quantum computer deutsch1985quantum  or a quantum Turing machine
bernstein1997quantum  provides a model to harness the complete power of
programmable quantum computation. Digital quantum simulation is a gate-based
approach where single and two-qubit quantum gates are used to implement
quantum operations and is closely related to universal quantum computation
arrazola2016digital . Quantum circuits are commonly used models for digital
quantum simulation yao1993quantum , where states in a Hilbert space are acted
upon by quantum operations using a collection of unitary matrices that map the
Hilbert space to itself nielsen1997programmable . Digital quantum simulation
of open quantum systems has gained attention only recently digital1 ; digital2
; digital3 ; perez ; digital4 ; digital5 ; digital6 ; 2 ; 3 ; 4 ; 5 ; 6 ;
nathan2020universal ; muller2011simulating ; sweke2014simulation ;
naikoo2020nonmarkovian . In perez , IBM Q-Experience simulator has been used
to implement paradigmatic open quantum dynamics such as amplitude damping and
entanglement pair generation. Discrete time quantum algorithms for studying
quantum channels has also been explored 2 ; 3 ; 4 ; 5 ; 6 ;
naikoo2020nonmarkovian .

The limited resources on a NISQ device poses several challenges for digital
quantum simulation preskill2020quantum . In this work, we present a general
methodology to design optimal quantum circuits for Markovian and Non-Markovian
open quantum systems. The methodology is developed systematically: First, we
use the notion of P-divisibility divisibility1 ; divisibility2 ; divisibility3
of a quantum channel to formulate operators for Markovian dynamics. We use
ancilla qubits to simulate the environment and note that tracing out the
ancilla induces memory-less evolution. Then, we propose a scheme for Non-
Markovian dynamics by duplicating the information on extra qubits, which are
not traced out and thus retain memory. We use a discrete-time approach and
simulate memory effects up to a finite order (i.e., the contributions from a
finite number of states in the past). Using the ancilla, we create a quantum
”register” to store information about past states, and update the register at
the end of every step using SWAP gates. We demonstrate simulation of amplitude
damping and dephasing of a qubit as examples. Non-Markovianity, in the sense
of P-indivisibility of the quantum circuits is inferred from the non-
monotonous behavior of the dynamics. These examples show that the methodology
is useful for simple open quantum system. Then, we generalize it to more
complex dynamics. We show that complex open quantum dynamics can be decomposed
into smaller processes with finite resource requirements. The complete
process, which generally needs parallel processing can be implemented
sequentially using the decomposition. Converting the parallel process into a
sequential one optimizes quantum space requirements, thus less number of
qubits are required. Since gate decomposition into elementary operations
becomes easier, number of gates also gets optimized. We simulate a Pauli
channel using this method, and show a reduction in number of qubits compared
to known methods.

This article is organized as follows. In Sec. II, an overview of open quantum
dynamics is given. In Sec. III quantum circuit for implementing the Markovian
and Non-Markovian dynamics are derived and in Sec. III.3 numerical simulations
of the quantum circuit models are presented is presented. In sec. IV, a
methodology for optimizing the quantum circuits is presented and the quantum
complexity analysis of implementation is discussed. Potential applications of
this work are discussed in Sec. V.

##  II Open quantum systems

The state of a quantum mechanical system is denoted by its wavefunction
$\ket{\psi}$ and the evolution of a system is given by the Schrodinger
equation,

$i\hbar\frac{d}{dt}\ket{\psi(t)}=H\ket{\psi(t)}.$ (1)

where $H$ is the Hamiltonian operator of the system. The Hamiltonian captures
the sum of kinetic and potential energy of the system. The solution of the
Schödinger equation is given by,

$\ket{\psi(t)}=U\ket{\psi(0)}=e^{-i\frac{H}{\hbar}t}\ket{\psi(0)}.$ (2)

The evolution is unitary as described by the operator $U$. In terms of the
density matrix $\rho$, the Schrödinger equation is written as,

$\frac{d\rho}{dt}=-i[H,\rho].$ (3)

Solving the above equation gives,

$\rho(t)=U\rho(0)U^{\dagger}.$ (4)

The above holds true for closed quantum systems. An open quantum system is a
part of a larger closed system, composed of the system $S$ and its environment
$E$. The Hilbert space of the total system $S+E$ is given by

${\mathcal{H}}_{SE}={\mathcal{H}}_{S}\otimes{\mathcal{H}}_{E},$ (5)

where ${\mathcal{H}}_{S}$ and ${\mathcal{H}}_{E}$ denote the Hilbert spaces of
$S$ and $E$, respectively.

To describe the evolution of an open quantum system, one considers the
evolution of the total system and traces out the environment at the end. A
common assumption made is that the initial state of the total system is of the
form,

$\rho_{SE}(0)=\rho_{S}(0)\otimes\rho_{E}(0).$ (6)

The state of the system at any time $t\geq 0$ is then described by,

$\rho_{S}(t)={\rm{tr}}_{E}\left\\{U(t)\rho_{S}(0)\otimes\rho_{E}(0)U^{\dagger}(t)\right\\}.$
(7)

This maps any initial state $\rho_{S}(0)$ to its final state using a dynamical
map $\Phi_{t}:\,S({\mathcal{H}}_{S})\longrightarrow S({\mathcal{H}}_{S})$
divisibility2 , such that,

$\rho_{S}(0)\mapsto\rho_{S}(t)=\Phi_{t}\rho_{S}(0).$ (8)

$\Phi_{t}$ is a positive map and thus, maps physical states to physical
states. Further, $\Phi_{t}$ is completely positive and admits a Kraus operator
representation,

$\Phi A=\sum_{i}\Omega_{i}A\Omega_{i}^{\dagger},$ (9)

for operator $A$, where $\Omega_{i}$ are Kraus operators and
$\sum_{i}\Omega_{i}^{\dagger}\Omega_{i}=I_{S}$. Open quantum dynamics can be
Markovian or Non-Markovian. This characterization is closely related to the
divisibility of the dynamical map. We describe these concepts below.

###  II.1 Divisibility and Markovianity

Let us define $\Phi_{t,s}$ as,

$\Phi_{t,s}=\Phi_{t}\Phi_{s}^{-1},\qquad t\geq s\geq 0,$ (10)

assuming that the inverse of $\Phi_{t}$ exists for all times $t\geq 0$, such
that,

$\Phi_{t,0}=\Phi_{t}~{}~{}~{}~{}\mbox{and}~{}~{}~{}~{}~{}\Phi_{t,0}=\Phi_{t,s}\Phi_{s,0}.$
(11)

Even though $\Phi_{t,0}$ and $\Phi_{s,0}$ are completely positive maps, the
map $\Phi_{t,s}$ need not be completely positive and not even positive since
the inverse $\Phi^{-1}_{s}$ of a completely positive map $\Phi_{s}$ need not
be positive.

Eq.(11) allows us to introduce the notion of divisibility. The family of
dynamical maps $\Phi=\left\\{\Phi_{t}\mid 0\leq t\leq T,\Phi_{0}=I\right\\}$
is said to be P-divisible if $\Phi_{t,s}$ is positive, and CP-divisible if
$\Phi_{t,s}$ is completely positive for all $t\geq s\geq 0$.

Divisibility of a dynamical map is closely related to the Markovianity of
evolution. In a Markovian process, the state of the system at the next moment
depends only on the current state of the system. In other words, the system
doesn’t have a memory of its previous states. In contrast, Non-Markovian
evolution depends on the previous states of the system. That is, the system
has memory of its previous states. In general, Markovian processes are
P-divisible, while Non-Markovian processes are not P-divisible. As we will see
in the next section, this classification allows us to derive models for
digital quantum simulation of open quantum systems.

##  III Quantum circuits for open systems

In this section, we give an overview of Markovian and Non-Markovian dynamics,
and describe the quantum circuits for simulating open quantum systems.

####  III.0.1 Markovian dynamics

To simulate open quantum systems on a quantum circuit, we can use ancillary
qubits to mimic the effect of environment. As discussed in the previous
section, Markovian dynamics have no memory of the previous states of the
system. That is, state at $n^{th}$ step depends only on the ${n-1}^{th}$ step.
Since the evolution only depends on the current state of the system, the
environment need not store information and the ancilla can be reset after each
step.

For Markovian evolution, $\rho_{S}(t+\delta t)$ only depends on $\rho_{S}(t)$.
Thus, in the discrete time setup, the evolution can be described as,

$\rho_{S}(t+\Delta
t)=\sum_{i}\Omega_{i}\rho_{S}(t)\Omega_{i}^{\dagger}=\Phi_{\Delta
t}\rho_{S}(t).$ (12)

The second equality holds due to divisibility of Markovian dynamics ( Eq.11).
Eq.(12) can be represented as a unitary evolution over system(S) +
environment(E) such that,

$\begin{split}\rho_{SE}(t)=&\rho_{S}(t)\otimes{\ket{0}\bra{0}}_{E},\text{and},\\\
\rho_{SE}(t+\Delta
t)=&\sum_{i}\Omega_{i}\rho_{S}(t)\Omega_{i}^{\dagger}\otimes{\ket{i}\bra{i}}_{E},\end{split}$
(13)

where $\ket{i}_{E}$ are the basis states of the environment. Tracing out the
environment from the above equation gives back Eq.(12). The unitary evolution
operator can be written as (using Stinespring dilation) preskillnotes ,

$\begin{split}&U_{SE}(\Delta
t)=\sum_{i}\Omega_{i}\otimes{\ket{i}\bra{0}}_{E}\\\ &\rho_{SE}(t+\Delta
t)=U_{SE}\Big{(}\rho_{S}(t)\otimes{\ket{0}\bra{0}}_{E}\Big{)}U_{SE}^{\dagger}\end{split}$
(14)

It can be verified that
$U_{SE}^{\dagger}U_{SE}=I_{S}\otimes\ket{0}\bra{0}_{E}$. This can be used to
simulate Markovian evolution by tracing out environment at the end of each
step and resetting it to $\ket{0}$ at the beginning of next step.

####  III.0.2 Non-Markovian dynamic

In Eq.(14), when we trace out the environment, we discard any information
about the previous step from the ancilla. This leads to memory less evolution.
The key idea behind simulating Non-Markovian systems is to retain some
information about the system in the ancillas.

Take an environment consisting of two qubits $E_{1}$ and $E_{2}$. Let
$\ket{i,j}_{E}=\ket{i}_{E_{1}}\ket{j}_{E_{2}}$, where $\ket{i}_{E}$ are the
basis states of the environment. Let,

$\rho_{SE}(t+\Delta
t)=\sum_{i}\Omega_{i}\rho_{S}(t)\Omega_{i}^{\dagger}\otimes{\ket{i,i}\bra{i,i}}_{E}.$
(15)

Here, we have duplicated the information on two environment qubits instead of
one qubit. So, if we trace out one of these, we will still have information
about this step on the other qubit.

After tracing out $E_{2}$ from Eq.(15) and resetting it to $\ket{0}_{E_{2}}$,
we get

$\rho_{SE}(t+\Delta
t)=\sum_{i}\Omega_{i}\rho_{S}(t)\Omega_{i}^{\dagger}\otimes{\ket{i,0}\bra{i,0}}_{E}.$
(16)

Now, if qubit $E_{1}$ controls the dynamics in the next step, this will lead
to backflow of information. Thus, we can create a memory for the system using
this method, leading to Non-Markovian dynamics.

In principle, we would need an infinite system to store information about the
state at all times in the past. However, we can overcome this by considering a
discrete-time setup (also suited for digital quantum simulation) and neglect
contributions beyond a certain order. That is, evolution at $n^{th}$ step
depends on last $k$ steps for some finite $k>1$. In such a case, we only need
to store information about $(n-1)^{th}$, $(n-2)^{th}$,…, $(n-(k-1))^{th}$
steps. Here, we are taking $k$ orders of contribution to evolution including
the contribution from the current ($n^{th}$) state. Thus, we need a way to
”store” the information about last $k-1$ steps, and update this information
after each new step. In addition we need to discard some information at the
end of each step. For example, for $k=3$, for $n^{th}$ step, we need to store
information about $(n-1)^{th}$ and $(n-2)^{th}$ step. Then, for $n+1)^{th}$
step, we need to store information about $(n)^{th}$ and $(n-1)^{th}$ step,
thus discarding information about $(n-2)^{th}$ step, and so on. This way, we
only need to store information on $k$ qubits at a time. Thus, we need qubits
$E_{1},\ldots,E_{k}$ for the environment.

Below, we describe in detail the quantum circuits for simulating Markovian and
Non-Markovian open quantum systems. We illustrate the methodology with the
help of two examples, amplitude damping and phase damping on a qubit. Later,
we show that this can be extrapolated to any open quantum system.

###  III.1 Example 1: Amplitude damping

####  III.1.1 Markovian

Amplitude damping of a qubit is represented by Kraus operators

$\Omega_{0}=\ket{0}\bra{0}+\sqrt{1-\gamma^{2}}\ket{1}\bra{1},\qquad\Omega_{1}=\gamma\ket{0}\bra{1}.$
(17)

The unitary operator for Markovian evolution ($U_{SE}(\Delta
t)=\Omega_{0}\otimes{\ket{0}\bra{0}}_{E}+\Omega_{1}\otimes{\ket{1}\bra{0}}_{E}$)
can be written as,

$\begin{split}&U_{SE}=\hat{S}\hat{C},\text{where}\\\
&\hat{C}=\ket{0}\bra{0}_{S}\otimes\ket{0}\bra{0}_{E}+\ket{1}\bra{1}_{S}\otimes
R_{y}(\theta)\ket{0}\bra{0}_{E},\\\
&\hat{S}=I_{S}\otimes\ket{0}\bra{0}_{E}+NOT_{S}\otimes\ket{1}\bra{1}_{E}.\end{split}$
(18)

Here, $\sin{\frac{\theta}{2}}=\gamma$ and $R_{y}$ is the rotation matrix about
y-axis on the Bloch sphere:
$R_{y}(\theta)\ket{0}=\sqrt{1-\gamma^{2}}\ket{0}+\gamma\ket{1}$. To verify
Eq.(18),

$\begin{split}\hat{S}\hat{C}=&\hat{S}.\\{\ket{0}\bra{0}_{S}\otimes\ket{0}\bra{0}_{E}\\\
&+\ket{1}\bra{1}_{S}\otimes\sqrt{1-\gamma^{2}}\ket{0}\bra{0}_{E}\\\
&+\ket{1}\bra{1}_{S}\otimes\gamma\ket{1}\bra{0}_{E}\\}\\\
=&\ket{0}\bra{0}_{S}\otimes\ket{0}\bra{0}_{E}\\\
&+\sqrt{1-\gamma^{2}}\ket{1}\bra{1}_{S}\otimes\ket{0}\bra{0}_{E}\\\
&+\gamma\ket{0}\bra{1}_{S}\otimes\ket{1}\bra{0}_{E}\\\
=&\\{\Omega_{0}\otimes{\ket{0}\bra{0}}_{E}+\Omega_{1}\otimes{\ket{1}\bra{0}}_{E}\\}.\end{split}$
(19)

This decomposition of the unitary evolution helps us simulate amplitude
damping using elementary gates.

Figure 1: Quantum circuit for implementing one step of Markovian amplitude
damping of a qubit. Here, $q$ and $e$ represent the qubit and environment
respectively. $e$ is set to $\ket{0}$ at the beginning of every step. Then,
the rotation operation on $e$ sets the right control to implement amplitude
damping using a $CNOT$ gate. The environment is traced out at the end of each
step. We can sequentially implement these steps to capture the complete
evolution.

Fig. 1 shows the quantum circuit for implementing amplitude damping of a
qubit. The unitary operator $U_{SE}$ is implemented using $\hat{C}$ and
$\hat{S}$ operators. $\hat{C}$ is implemented using the controlled rotation
gate and $\hat{S}$ operator is implemented using the $CNOT$ gate. The
environment is traced out at the end of a step to induce Markovianity in the
dynamics. The figure shows one step of the dynamics (comprising of operations
in the box), which can be repeated to implement the complete evolution.

Thus, by mapping an amplitude damping channel to unitary evolution on a larger
system, we could design quantum circuits for its simulation. Here, we
considered a Markovian process. Next, we formulate the quantum circuits for
Non-Markovian amplitude damping.

####  III.1.2 Non-Markovian

In the above case, the $R_{y}(\theta)$ gate is used to control the effect of
the environment on the qubit. $\theta$ captures the first order contribution
to the Markovian dynamics. When we trace out $e$ in Fig. 1, we discard all the
information about the previous state of the system. To introduce memory
effects, we use extra environment qubits which are able to store this
information and simulate higher order contributions in Non-Markovian systems.
Below, we illustrate and explain the quantum circuit implementation for Non-
Markovian amplitude damping of a qubit, with three orders of contributions
(k=3) to memory in the dynamics.

Figure 2: Quantum circuit for implementing one step of Non-Markovian amplitude
damping of a qubit. Here, $q$ and $e_{i}$ represent the qubit and environment
respectively. $R_{y}(\theta_{i})$ is used to ”store” contributions of current
state to $i^{th}$ order dynamics. Amplitude damping of the qubit is
implemented using a $CNOT$ gate. $e_{1}$ is traced out at the end of each step
and reset to $\ket{0}$ and SWAP gates are used to update the environment
states before the next step. We can sequentially implement these steps to
capture the complete evolution (Fig. 3).

Fig. 2 shows the quantum circuit for implementing one step of Non-Markovian
evolution. Here, $q$ represents the qubit under amplitude damping and
$e_{1},e_{2},e_{3}$ represent the environment. Controlled rotation matrices
$R_{y}(\theta^{i})$, for $i\in{1,2,3}$ are used to capture the contribution of
the current state to $i^{th}$ order dynamics. $i^{th}$ order dynamics at a
particular time $t$, is due to contribution from state at time $t-i$. Thus, we
need to store information about a state for future retrieval. The
controlled-$R_{y}(\theta^{1})$ operation on $e_{1}$ captures first order
contribution, similar to the Markovian case (Fig. 1). Then, we store
information about the current state on $e_{2}$ and $e_{3}$ for contributions
to future steps using controlled-$R_{y}(\theta^{2/3})$. The $CNOT$ gate is
used to implement the amplitude damping ($\ket{1}\to\ket{0}$) in current
state. $e_{1}$ is then traced out and reset to $\ket{0}$ state.

After this, the first $SWAP$ gate exchanges the state of $e_{1}$ and $e_{2}$.
Thus, the state of $e_{1}$ becomes $R_{y}(\theta^{2})\ket{0}$ and the state of
$e_{2}$ becomes $\ket{0}$. Similarly, after the next SWAP gate, the state of
$e_{2}$ becomes $R_{y}(\theta^{3})\ket{0}$ and the state of $e_{3}$ becomes
$\ket{0}$. Here, we have assumed for now that $e_{2}$ and $e_{3}$ were
initially in state $\ket{0}$. So, the states of ${e_{1}},{e_{2}},\text{ and
}{e_{3}}$ are $R_{y}(\theta^{2})\ket{0},R_{y}(\theta^{3})\ket{0},\text{ and
}\ket{0}$ respectively. Thus, before the next step $e_{1}$ is is correlated
with the qubit and carries information about the previous step.

Fig. 3 shows implementation of complete Non-Markovian evolution by sequential
application of steps. In the second step, $e_{1}$ already carries information
from the previous step. Thus, when we implement controlled rotation matrix
$R_{y}(\theta^{1})$, $e_{1}$ carries contributions from both the current
($\theta^{1}$) and the previous step ($\theta^{2}$). Similarly, after
controlled rotation matrix $R_{y}(\theta^{2})$, $e_{2}$ carries contributions
of $\theta^{2}$ due to current step and $\theta^{3}$ due to previous step.
After controlled rotation matrix $R_{y}(\theta^{3})$, $e_{3}$ only carries
information due to current step, as it was in state $\ket{0}$ at the
beginning. Then, implementing the $CNOT$ gate using $e_{1}$ in the second step
not only captures first order effects due to $\theta^{1}$, but also second
order effects coming from $\theta^{2}$ which was entangled with the state of
the system in the previous step. This capture the memory effect of the bath
when we trace out $e_{1}$ and reset to $\ket{0}$.

Figure 3: Quantum circuit for Non-Markovian amplitude damping of a qubit, by
sequentially implementing the steps (boxes).

Applying the two SWAP gates again, leads to $e_{1}$ carrying contributions due
to $\theta^{2}$ and $\theta^{3}$, $e_{2}$ carrying contributions due to
$\theta^{3}$, and $e_{3}$ is in state $\ket{0}$. Thus, when we implement
controlled rotation matrices $R_{y}(\theta^{1})$ of step 3, $e_{1}$ carries
contributions from $\theta^{1}$ due to current step, and $\theta^{2}$ and
$\theta^{3}$ due to previous steps. Again, $e_{2}$ carries contributions of
$\theta^{2}$ due to current step and $\theta^{3}$ due to previous step. Then,
implementing the $CNOT$ gate using $e_{1}$ in the third step captures first,
second and third order contributions. Thus, we are able to model memory
effects in the evolution. Similar analysis holds for the following steps,
where we $e_{1}$ always captures contribution from $k=3$ orders of dynamics.

Overall, the idea is to trace out only a part of the environment (only $e_{1}$
is traced out, $e_{2}$ and $e_{3}$ are not measured) and then introduce
appropriate evolution within the environment to retain some of the coherence
for the next step, thus modeling memory effects. In the above example, we used
$e_{2}$ and $e_{3}$ to store appropriate information about the history of the
system, and used $e_{1}$ to implement the current step. The information was
updated at the end of each step using SWAP gates which ”shift” the information
up by one order to prepare for the next step. This methodology can be extended
to any Non-Markovian open quantum system. Next, we use it to model dephasing
of a qubit.

###  III.2 Example 2: Dephasing of a qubit

Here, we illustrate another example of Markovian and Non-Markovian process. We
follow the same methodology as presented above: First, we write the Kraus
representation of the dynamics and use Stinespring dilation to find a unitary
operator for simulating the system along with the environment. Then, we
decompose the unitary operator into elementary gates to formulate quantum
circuits for the dynamics. After obtaining a model for Markovian process, we
generalize it to Non-Markovian process by adding extra environment qubits that
store information. We partially trace out the environment at the end of a
step, and use SWAP gates to update the information stored on qubits for the
next step. This helps to model memory effects in the dynamics. Below, we apply
this methodology to dephasing of a qubit.

Markovian dephasing can be written in the Kraus representation as,

$\begin{split}\rho_{S}(t+\Delta
t)=\Omega_{0}\rho_{S}(t)\Omega_{0}^{\dagger}+\Omega_{1}\rho_{S}(t)\Omega_{1}^{\dagger}\\\
\Omega_{0}=\sqrt{1-\gamma^{2}}I_{S},\qquad\Omega_{1}=\gamma Z_{S}.\end{split}$
(20)

The unitary operator for Markovian evolution ($U_{SE}(\Delta
t)=\Omega_{0}\otimes{\ket{0}\bra{0}}_{E}+\Omega_{1}\otimes{\ket{1}\bra{0}}_{E}$)
can be written as,

$\begin{split}&U_{SE}=\hat{S}\hat{C}\\\ &\hat{C}=I_{S}\otimes
R_{y}(\theta)\ket{0}\bra{0}_{E}\\\
&\hat{S}=I_{S}\otimes\ket{0}\bra{0}_{E}+Z_{S}\otimes\ket{1}\bra{1}_{E}\end{split}$
(21)

where $\sin{\frac{\theta}{2}}=\gamma$,
$R_{y}(\theta)\ket{0}=\sqrt{1-\gamma^{2}}\ket{0}+\gamma\ket{1}$. This can be
proven as,

$\begin{split}\hat{S}\hat{C}=\hat{S}.\\{I_{S}\otimes\sqrt{1-\gamma^{2}}\ket{0}\bra{0}_{E}+I_{S}\otimes\gamma\ket{1}\bra{0}_{E}&\\}\\\
=\sqrt{1-\gamma^{2}}I_{S}\otimes\ket{0}\bra{0}_{E}+\gamma
Z_{S}\otimes\ket{1}\bra{0}_{E}&\\\
=\\{\Omega_{0}\otimes{\ket{0}\bra{0}}_{E}+\Omega_{1}\otimes{\ket{1}\bra{0}}_{E}\\}&.\end{split}$
(22)

Figure 4: Quantum circuit for implementing one step of Markovian dephasing of
a qubit. Here, $q$ and $e$ represent the qubit and environment respectively.
$e$ is set to $\ket{0}$ at the beginning of every step. Then, the rotation
operation on $e$ sets the right control to implement dephasing using a $CZ$
gate. The environment is traced out at the end of each step. We can
sequentially implement these steps to capture the complete evolution.

Fig. 4 shows the quantum circuit for implementing dephasing of a qubit. The
unitary operator $U_{SE}$ is implemented using $\hat{C}$ and $\hat{S}$
operators. $\hat{C}$ is implemented using the rotation gate and $\hat{S}$
operator is implemented using the $CZ$ gate, as shown in the figure. The
environment is traced out at the end of a step. One complete step (comprising
of operations in the box) can be repeated to implement the complete evolution.

Figure 5: Quantum circuit for implementing one step of Non-Markovian dephasing
of a qubit. Here, $q$ and $e_{i}$ represent the qubit and environment
respectively. $R_{y}(\theta_{i})$ is used to ”store” contributions of current
state to $i^{th}$ order dynamics. Dephasing of the qubit is implemented using
a $CZ$ gate. $e_{1}$ is traced out at the end of each step and reset to
$\ket{0}$ and SWAP gates are used to update the environment states before the
next step. We can sequentially implement these steps to capture the complete
evolution.

Fig. 5 shows quantum circuit for dephasing of a qubit with $k=3$ orders of
contribution. Similar to the analysis in the previous example, the circuit
here will exhibit memory effects and lead to Non-Markovian dynamics.

###  III.3 Numerical Simulations

Here we present numerical simulations of the quantum circuit models presented
above. Fig. 6 shows the evolution of population densities in state $\ket{1}$
of a qubit under Markovian and Non-Markovian amplitude damping. The initial
state of the qubit $\rho(0)=\ket{1}\bra{1}$. The dynamics are simulated for
the circuits shown in Fig. 1 and Fig. 2. For the Markovian case, the
population in $\ket{1}$ slowly dies off and gets transferred to state
$\ket{0}$ through amplitude damping. Here, we have taken $\theta=\pi/10$,
Eq.(18). For the Non-Markovian case, the population in $\ket{1}$ oscillates
while decreasing. Here, we have taken $\theta^{1}=\pi/10$,
$\theta^{2}=2\pi/3$, and $\theta^{3}=5\pi/6$, Fig. 2. From the two plots, we
can note that the quantum circuit models capture the features of Markovian and
Non-Markovian systems. For plot 1, the decay in population is strictly
monotonic, which is characteristic of Markovian evolution. In Non-Markovian
evolution, we can observe the non-monotonic behavior due to memory effects of
the environment. Comparing the two, we can see that population in state
$\ket{1}$ sustains for longer due to memory in Non-Markovian case.

Figure 6: Evolution of the population density of state $\ket{1}$ for a qubit
under amplitude damping. Markovian dynamics are calculated according to Fig. 1
and Non-Markovian dynamics are calculated according to Fig. 2. Figure 7:
Evolution of the population density of state $\ket{+}$ (Hadamard basis) for a
qubit under phase damping. Markovian dynamics are calculated according to Fig.
4 and Non-Markovian dynamics are calculated according to Fig. 5.

Fig. 7 shows the simulations of the phase damping model. The population is
plotted in the Hadamard basis to show the effect of phase damping. The initial
state of the qubit is $\ket{+}=\frac{\ket{0}+\ket{1}}{\sqrt{2}}$. For the
Markovian case, the population in $\ket{+}$ slowly dies off and gets
transferred to state $\ket{-}$ through phase damping. Here, we have taken
$\theta=\pi/5$, Eq.(21). For the Non-Markovian case, the population in
$\ket{+}$ oscillates while decreasing. Here, we have taken $\theta^{1}=\pi/5$,
$\theta^{2}=\pi/4$, and $\theta^{3}=\pi/2$, Fig. 5. For plot 1, the decay in
population is strictly monotonic, which is characteristic of Markovian
evolution. In Non-Markovian evolution, we can observe the non-monotonic
behavior due to memory effects of the environment. Comparing the two, we can
see that population in state $\ket{+}$ oscillates for longer due to memory in
Non-Markovian case. In both plots, the final population tends to $0.5$.

Figure 8: Evolution of the population density of state $\ket{1}$ for a qubit
under amplitude damping. Due to memory effects, population in state $\ket{1}$
in Non-Markovian dynamics sustains despite amplitude damping. Markovian
dynamics are calculated according to Fig.,1 and Non-Markovian dynamics are
calculated according to Fig. 2.

Fig. 8 shows another example of amplitude damping of a qubit. Here, we take
$\theta^{1}=\pi/8$ for the Markovian case, and $\theta^{1}=\pi/8$,
$\theta^{2}=5\pi/6$, and $\theta^{3}=\pi$ for the Non-Markovian case. We can
note that this figure greatly differs from Fig. 6. Here, the memory effects
lead to population in state $\ket{1}$ to sustain despite amplitude damping.
This shows that Non-Markovian phenomena are quite interesting and can show
varied dynamics.

Thus, the quantum circuit models presented in the two examples capture the
appropriate Markovian and Non-Markovian dynamics. These examples can be used
to extrapolate the methodology to other cases. In the next section, we analyze
the complexity of the quantum circuits and optimize the implementation for
general open quantum systems,

##  IV Complexity analysis and optimization

In amplitude damping (or phase damping) through a Markovian process, we used
$1$ qubit to represent the system, and one qubit to simulate the environment,
Fig. 1, and 4. In general, for a system with Hilbert space dimension $n$, we
need $\log n$ qubits for simulation. We had arrived at a quantum circuit model
for open quantum systems using Stinespring dilation of the Kraus
representation, ,Eq.(13). For a Kraus representation consisting of $l$ terms
in the sum, we need atleast $\log l$ qubits for the environment. For the
amplitude damping (or phase damping) case, $l=2$, thus one qubit was needed
for simulating the environment. In general, $O(l)$ different qubits are used
to simulate such dynamics. For example, in perez  $3$ ancilla are used for a
decohering qubit (under simultaneous damping under the 3 Pauli operators).
Such an implementation needs $O(\log n)$ qubits for the system + $O(l)$ qubits
for the bath. Below, we propose a scheme with reduction in number of
environment qubits to $O(1)$ (i.e. constant) for any $l$.

Consider a Markovian quantum channel with Kraus representation,

$\Phi_{t}:\rho_{S}(t)=\sum_{i=1}^{l}\Omega_{i}\rho_{S}(0)\Omega_{i}^{\dagger}.$
(23)

The usual Stinespring dilation gives,

$U_{SE}=\sum_{i=1}^{l}\Omega_{i}\otimes\ket{i}\bra{0}_{E}.$ (24)

By implementing $U_{SE}$ and tracing out the environment, we can simulate the
quantum channel. When we implement $U_{SE}$ gate, we are simultaneously
implementing the Kraus operators. In transport , a method is proposed where
the simultaneous process is instead implemented sequentially using lesser
number of qubits. The method is summarized below. In transport , this method
is used for simulating environment assisted quantum transport. Here, we have
generalized it to any open quantum system.
Consider a channel given by,

$\rho_{S}(t)=\sum_{i=1}^{l}\Omega_{i}\rho_{S}(0)\Omega_{i}^{\dagger}.$ (25)

The Kraus representation can be decomposed as,

$\Phi_{t}=\Phi_{t}^{l}\circ\Phi_{t}^{l-1}\circ\ldots\circ\Phi_{t}^{1}$ (26)

where,

$\Phi_{t}^{i}(\rho_{S})=\Omega_{i}\rho_{S}\Omega_{i}^{\dagger}+\Omega_{i}^{\prime}\rho_{S}\Omega_{i}^{\prime\dagger}.$
(27)

Now,

$\Phi_{t}^{j}\circ\Phi_{t}^{i}=\Omega_{i}\rho_{S}\Omega_{i}^{\dagger}+\Phi_{t}^{j}(\Omega_{i}^{\prime}\rho_{S}\Omega_{i}^{\prime\dagger}),$
(28)

for $\Omega_{i}^{\prime}=\sqrt{I-\Omega_{i}^{\dagger}\Omega_{i}}$. And,

$\Omega_{i}^{\prime}\approx I-\frac{1}{2}\Omega_{i}^{\dagger}\Omega_{i}.$ (29)

Thus,

$\Omega_{i}^{\prime}\rho_{S}\Omega_{i}^{\prime\dagger}\approx\rho_{S}-\frac{1}{2}\Omega_{i}^{\dagger}\Omega_{i}\rho_{S}-\frac{1}{2}\rho_{S}\Omega_{i}^{\dagger}\Omega_{i}.$
(30)

To prove Eq.(26), consider the second term in Eq.(28),

$\Phi_{t}^{j}(\Omega_{i}^{\prime}\rho_{S}\Omega_{i}^{\prime\dagger})=\Omega_{j}(\Omega_{i}^{\prime}\rho_{S}\Omega_{i}^{\prime\dagger})\Omega_{j}^{\dagger}+\Omega_{j}^{\prime}(\Omega_{i}^{\prime}\rho_{S}\Omega_{i}^{\prime\dagger})\Omega_{j}^{\prime\dagger}.$
(31)

Substituting Eq.(30) and taking terms only upto first order we get,

$\begin{split}\Phi_{t}^{j}(\Omega_{i}^{\prime}\rho_{S}\Omega_{i}^{\prime\dagger})=\Omega_{j}\rho_{S}\Omega_{j}^{\dagger}+\rho_{S}&-\frac{1}{2}\Omega_{i}^{\dagger}\Omega_{i}\rho_{S}-\frac{1}{2}\rho_{S}\Omega_{i}^{\dagger}\Omega_{i}\\\
&-\frac{1}{2}\Omega_{j}^{\dagger}\Omega_{j}\rho_{S}-\frac{1}{2}\rho_{S}\Omega_{j}^{\dagger}\Omega_{j}.\end{split}$
(32)

Substituting back in Eq.(28),

$\begin{split}\Phi_{t}^{j}\circ\Phi_{t}^{i}=\Omega_{i}\rho_{S}\Omega_{i}^{\dagger}+\Omega_{j}\rho_{S}\Omega_{j}^{\dagger}+\rho_{S}\\\
-\frac{1}{2}\Omega_{i}^{\dagger}\Omega_{i}\rho_{S}-\frac{1}{2}\rho_{S}\Omega_{i}^{\dagger}\Omega_{i}\\\
-\frac{1}{2}\Omega_{j}^{\dagger}\Omega_{j}\rho_{S}-\frac{1}{2}\rho_{S}\Omega_{j}^{\dagger}\Omega_{j}.\end{split}$
(33)

Composing all maps, Eq.(26) will give,

$\begin{split}\Phi_{t}^{l}\circ\Phi_{t}^{l-1}\circ\ldots\circ\Phi_{t}^{1}=&\sum_{i=1}^{l}\Omega_{i}\rho_{S}\Omega_{i}^{\dagger}+\rho_{S}\\\
-\frac{1}{2}&\sum_{i=1}^{l}\Omega_{i}^{\dagger}\Omega_{i}\rho_{S}-\frac{1}{2}\sum_{i=1}^{l}\rho_{S}\Omega_{i}^{\dagger}\Omega_{i}.\end{split}$
(34)

Now, $\sum_{i=1}^{l}\Omega_{i}^{\dagger}\Omega_{i}=I$. Thus, the last two
terms above are $=\frac{1}{2}\rho_{S}$.

Sum of last three terms in Eq.(34):
$\rho_{S}-\frac{1}{2}\rho_{S}-\frac{1}{2}\rho_{S}=0$.

Thus,

$\Phi_{t}^{l}\circ\Phi_{t}^{l-1}\circ\ldots\circ\Phi_{t}^{1}=\sum_{i=1}^{l}\Omega_{i}\rho_{S}\Omega_{i}^{\dagger}=\Phi_{t}.$
(35)

Figure 9: Quantum circuit for optimizing resource requirements (qubits and
gates) by converting a parallel process in to a sequential one ( Eq.26). Here,
decoherence of a qubit is modeled. $c$ is the control qubit, $q$ is the
system, and $e$ simulates the environment. One step(box) consists of
sequential implementation of appropriate $X$, $Y$, and $Z$ gates.

This proves that we can sequentially implement Kraus operators to simulate a
quantum channel. Fig.9 shows the quantum circuit for a decohering qubit. Here,
we have sequentially applied the Kraus operations using an extra control qubit
$c$. This helps in implementing the decomposition map so that $\ket{0}$ state
of $c$ is used to simulate Kraus operators sequentially (using the composition
of maps Eq.(26)). $e$ is traced out and reset after implementing each Pauli
operator and $c$ is traced out after one complete step. Here, we have shown
the quantum circuit for Markovian evolution. The same can be used for Non-
Markovian evolution, by adding environment qubits, as illustrated in the
previous section.

Complexity Analysis:
We need $\log n$ qubits for implementing a quantum system with Hilbert space
$dim=n$. We can implement the effect of environment by using $k$ qubits (as
described in previous section), where $k$ is the order upto which we are
taking memory effects. For optimization using sequential implementation, one
extra qubit is needed as control. Thus,
Total number of qubits $=O(\log n+k)$

To implement each Kraus operation, we need $2$ gates (rotation of environment
qubit + implementation of operation). If there are $l$ operators in the Kraus
representation, we will need $O(l)$ gates. This holds for Markovian processes.
For Non-Markovian evolution, we need additional $O(k)$ gates ($k$ rotation
gates for memory, plus $k-1$ SWAP gates for updating the environment after
each step, see Fig. 2). Thus,
Number of gates in one step= $O(k+l)$
Number of gates in complete evolution= $O(T(k+l))$, where $T$ is the total
(discrete-)time.

The quantum complexity obtained above is a reduction over the usual method for
simulation. For example, $O(\log n+k\log l)$ qubits are needed to simulate a
quantum channel using the existing method of Stinespring dilation. Further,
Suzuki-Lie Trotter decomposition of general unitary gates over q number of
qubits takes $O(\exp{q})$ gates. Thus, for Stinespring dilation $O(l^{k})$
gates are needed.

Thus, the quantum circuits proposed in this article, along with a method for
sequential implementation of operations can be used to simulate both Markovian
and Non-Markovian open quantum systems. Further, the obtained circuits are
optimal in both time, and space requirements.

##  V Conclusion

We have presented a general framework to develop quantum circuits for digital
quantum simulation of Markovian and Non-Markovian open quantum systems. The
environment is simulated using ancilla qubits which control the dynamics on
the system. For Markovian dynamics, the environment is traced out after each
step and reset to $\ket{0}$. For Non-Markovian systems, the environment is
only partially traced out so as to retain information for the next step. This
helps create a memory of the system, which is updated at the end of each step
using SWAP gates. Numerical simulations of these models reproduce the
characteristic monotonic behavior for Markovian systems, and oscillations due
to memory effects in Non-Markovian systems. Further, we have introduced a
method to optimize resource requirements for simulating quantum channels. The
method relies of converting a parallel process to a sequential one, thus
reducing space requirements. It employs simple quantum gates (controlled
rotation and CNOTs) which reduce time complexity when compared to the widely
used Stinespring dilation method. The Markovian and Non-Markovian quantum
circuits, together with a method for optimizing complex processes provides an
optimal framework to simulate any open quantum system.

Open quantum systems are generally simulated on analog quantum simulators,
with digital quantum simulation being studied only recently. The models
presented in this article provide a promising framework to simulate open
quantum systems on digital-NISQ technology. For example, due to small resource
requirement, the quantum circuits can be used to implement complex open
quantum systems on IBM Q-Experience perez . The framework can also be used to
understand Non-Markovian dynamics in various contexts, by tuning parameters
like $\theta^{i}$, $k$, etc., since it is simpler to use than the more common
HEOM (Hierarchical equations of motion), Nakajima-Zwanzig equation, or other
models. An interesting line of work could be to explore how the different
theoretical models relate to each other. Further, it might be useful to study
the implications of the optimization presented here, to larger scale quantum
computing. Another potential application could be to study reservoir
engineering on quantum simulators, so that the memory effects can be used to
create long-term coherence as observed in Fig. 8.

## References

  * (1) H.P. Breuer and F. Petruccione. The theory of open quantum systems. Oxford University Press on Demand (2002).
  * (2) A. Rivas, and S. F. Huelga. Open quantum systems. Vol. 13. Berlin: Springer (2012).
  * (3) B. Vacchini. Decoherence and noise in open quantum system dynamics Fluct. Noise Lett., 15, 1640003 (2016)
  * (4) J. Lammers, H. Weimer, Klemens Hammerer. Open-system many-body dynamics through interferometric measurements and feedback. Phys. Rev. A 94, 052120 (2016)
  * (5) R. Clifton, H. Halvorson. Entanglement and Open Systems in Algebraic Quantum Field Theory. Stud. Hist. Philos. Mod.Phys. 32 1-31 (2001)
  * (6) V. Gorini et al. Completely positive dynamical semigroups of N‐level systems. J. Math. Phys. 17, 821 (1976);
  * (7) M. A. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press (2000).
  * (8) J.R.Johansson, P.D.Nation, F. Nori. QuTiP: An open-source Python framework for the dynamics of open quantum systems Comput. Phys. Commun. 183 1760 (2012)
  * (9) J. Preskill. Quantum Computing in the NISQ era and beyond. Quantum 2, 79 (2018).
  * (10) A.Smith, M. S. Kim, F. Pollmann, et al. Simulating quantum many-body dynamics on a current digital quantum computer. npj Quantum Information 5, 106 (2019).
  * (11) A. Chiuri et al. Linear Optics Simulation of Quantum Non-Markovian Dynamics. Sci Rep 2, 968 (2012).
  * (12) BH. Liu et al. Experimental control of the transition from Markovian to non-Markovian dynamics of open quantum systems. Nature Phys 7, 931–934 (2011).
  * (13) A. Cuevas et al. All-optical implementation of collision-based evolutions of open quantum systems. Sci Rep 9, 3205 (2019).
  * (14) S. Mostame, J. Huh, C. Kreisbeck, et al. Emulation of complex open quantum systems using superconducting qubits. Quantum Inf Process 16, 44 (2017).
  * (15) S. Mostame, et al. Quantum simulator of an open quantum system using superconducting qubits: exciton transport in photosynthetic complexes. New J. Phys. 14 105013 (2012)
  * (16) David Deutsch. Quantum theory, the Church–Turing principle and the universal quantum computer. Proc. R. Soc. Lond. A 400: 97–117 (1985)
  * (17) E. Bernstein and U. Vazirani. Quantum Complexity Theory SIAM J. Comput., 26 (5), 1411–1473. (1997)
  * (18) I. Arrazola, J. Pedernales, L. Lamata. et al. Digital-Analog Quantum Simulation of Spin Models in Trapped Ions.  Sci Rep. 6, 30534 (2016).
  * (19) A. Chi-Chih Yao. Quantum circuit complexity. Proc. of IEEE 34th Annual Foundations of Computer Science, Palo Alto, CA, USA (1993)
  * (20) M. A. Nielsen and I. L. Chuang. Programmable Quantum Gate Arrays Phys. Rev. Lett. 79, 321 (1997)
  * (21) G.A.L. White et al. Demonstration of non-Markovian process characterisation and control on a quantum processor. Nat Commun 11, 6301 (2020).
  * (22) H. Wang, S. Ashhab, and F. Nori. Quantum algorithm for simulating the dynamics of an open quantum system. Phys. Rev. A 83, 062317 (2011).
  * (23) P. Schindler et al. Quantum simulation of dynamical maps with trapped ions. Nature Phys 9, 361–367 (2013).
  * (24) G. García-Pérez, M.A.C. Rossi, and S. Maniscalco. IBM Q Experience as a versatile experimental testbed for simulating open quantum systems. npj Quantum Inf 6, 1 (2020).
  * (25) D. Wang, D. W. Berry, M. C. de Oliveira, B. C. Sanders. Solovay-Kitaev Decomposition Strategy for Single-Qubit Channels. Phys. Rev. Lett. 111, 130504 (2013).
  * (26) H. Lu et al. Experimental quantum channel simulation. Phys. Rev. A 95, 042310
  * (27) T. Xin. Quantum simulation of quantum channels in nuclear magnetic resonance. Phys. Rev. A 96, 062303 (2017).
  * (28) G. Kemp, I. Sinayskiy, and F. Petruccione. Lazy open quantum walks. Phys. Rev. A 102, 012220 (2020).
  * (29) A. J. van Wonderen and K. Lendi. Non-Markovian quantum dissipation in the Kraus representation. EPL 71 737 (2005).
  * (30) B. Bylicka, D. Chruściński, and S. Maniscalco. Non-Markovianity and reservoir memory of quantum channels: a quantum information theory perspective. Sci Rep 4, 5720 (2014).
  * (31) S. Attal et al. Open quantum walks on graphs. Physics Letters A 376 1545–1548 (2012).
  * (32) Z. Hu, R. Xia, and S. Kais. A quantum algorithm for evolving open quantum dynamics on quantum computing devices. Sci Rep 10, 3301 (2020).
  * (33) F. Nathan, M. S. Rudner. Universal Lindblad equation for open quantum systems. Phys. Rev. B 102, 115109 (2020)
  * (34) M. Müller, et al. Simulating open quantum systems: from many-body interactions to stabilizer pumping. New J. Phys. 13 085007 (2011).
  * (35) R. Sweke, I. Sinayskiy, and F. Petruccione. Simulation of single-qubit open quantum systems Phys. Rev. A 90, 022331 (2014)
  * (36) J. Naikoo, S. Banerjee, C. M. Chandrashekar. Non-Markovian channel from the reduced dynamics of coin in quantum walk. arXiv:2007.09896.
  * (37) J. Preskill, Quantum computing: Current status and future prospects. Bulletin of the American Physical Society 65 (2020).
  * (38) A. Rivas, S. F. Huelga, and M. B. Plenio. Quantum non-Markovianity: characterization, quantification and detection. Rep. Prog. Phys. 77, 094001 (2014).
  * (39) H.-P. Breuer, E.-M. Laine, J. Piilo, and B. Vacchini. Colloquium: Non-Markovian dynamics in open quantum systems. Rev. Mod. Phys. 88, 021002 (2016).
  * (40) U. Shrikant, R. Srikanth, and S. Banerjee. Temporal self-similarity of quantum dynamical maps as a concept of memorylessness. Sci Rep 10, 15049 (2020).
  * (41) Preskill, John. Lecture notes for physics 229: Quantum information and computation. California Institute of Technology 16 (1998).
  * (42) P. Gupta, and C. M. Chandrashekar. Digital quantum simulation framework for energy transport in an open quantum systems. New J. Phys. in press. (2020).