Copyright for this paper by its authors. Use permitted under Creative Commons
License Attribution 4.0 International (CC BY 4.0).

2nd Edition of EvalRS: a Rounded Evaluation of Recommender Systems, August 6 -
August 10, 2023, Long Beach, CA, USA

[orcid=0000-0001-6438-366X<EMAIL_ADDRESS>] [1]

[orcid=0000-0001-7458-5281<EMAIL_ADDRESS>]

[orcid=0000-0003-1433-0089<EMAIL_ADDRESS>]

[1]Corresponding author.

# Bridging Offline-Online Evaluation with a Time-dependent and Popularity
Bias-free Offline Metric for Recommenders

Petr Kasalický  Faculty of Information Technology, Czech Technical University
in Prague, Thákurova 9, Prague, 160 00, Czech Republic  Rodrigo Alves  Pavel
Kordík

(2023)

###### Abstract

The evaluation of recommendation systems is a complex task. The offline and
online evaluation metrics for recommender systems are ambiguous in their true
objectives. The majority of recently published papers benchmark their methods
using ill-posed offline evaluation methodology that often fails to predict
true online performance. Because of this, the impact that academic research
has on the industry is reduced. The aim of our research is to investigate and
compare the online performance of offline evaluation metrics. We show that
penalizing popular items and considering the time of transactions during the
evaluation significantly improves our ability to choose the best
recommendation model for a live recommender system. Our results, averaged over
five large-size real-world live data procured from recommenders, aim to help
the academic community to understand better offline evaluation and
optimization criteria that are more relevant for real applications of
recommender systems.

###### keywords:

recall click-through rate leave-last-one-out evaluation popularity bias

##  1 Introduction

The evaluation of recommendation systems is a complex task. One of the primary
reasons is that several evaluation metrics represent distinct properties of a
recommendation algorithm (RA). For instance, RMSE is a reliable marker of how
a RA predicts a user-to-item taste [1], whereas Recall reflects how well the
same algorithm retrieves a relevant list of items [2]. Therefore, it is
crucial to identify metrics that effectively evaluate and describe the target
of a particular recommender system (RS).

A comprehensive search of the relevant literature revealed that the most
prevalent method is _offline_ evaluation of static feedback, where data are
collected from a real-world RS dataset [3, 4]. In offline evaluation,
recommendation algorithms are trained on a training subset of data [5], and
then their recommendations are evaluated on test data using metrics such as
Recall@$k$ [6], Precision@$k$ [7], NDCG@$k$ [8], MAP@$k$ [9] and HR@$k$ [10].

However, conventional offline evaluation of RS has significant disadvantages.
For instance, the interaction observation follows a non-uniform distribution
[11, 12, 13]: certain items have more interaction observations solely because
the RS exposed them to more users. In addition to observation bias, standard
offline evaluation techniques are agnostic to the fact that recommendation
algorithms perform in a live environment where it is only possible to use
interactions made in the past to predict future interactions: the commonly
employed leave-one-out-cross-validation (LOOCV) method [14, 15] does not track
the user’s behavior over time.

Several approaches have been proposed to address these drawbacks. Bias in the
test data caused by the missing-not-at-random (MNAR) problem can be partially
suppressed by sampling [16, 17] or by using popularity-stratified recall [13],
which gives a higher reward for recommending less popular items. The unbiased
evaluation method for simulating bandit algorithms introduced in [18] was
experimentally verified in [19] and found to work only for Top-1
recommendations.

Regarding time-aware validation processes, [20] proposed leave-last-one-out-
cross-validation (LLOOCV), where the validation set only considers the latest
iteration of each user. Although there is a clear past-future distinction for
each user, in LLOOCV there is no such distinction between users. [21] offered
a more comprehensive solution called $k$-fold Sliding Window Evaluation (SW-
EVAL), which analyzes the recommendation algorithm based only on interactions
that occurred after the conclusion of the training data.

Unfortunately, despite the significant progress made by the RS community to
debiasing offline evaluation, the techniques often do not adequately reflect
the nature of _online_ recommender systems. An optimal evaluation technique
should review the entire system and consider the platform’s high-level
objectives, such as the number of clicks on items, the number of items
purchased, the number of adverts viewed, the customer lifetime value, etc.
[22]. Such metrics are unsuitable for the offline setting because a RS’s
environment is domain-dependent, dynamic, and constantly changing.
Furthermore, the results are frequently unreproducible because they are based
on the monitoring of implicit interactions of a real user or asking them to
use pop-up surveys for explicit ratings of the recommended items [23].

This paper fulfills the research objectives outlined for the EvalRS 2023
workshop [24] by experimentally exploring the relationship between offline and
online metrics. We note that this comparison type is crucial for real-world
recommenders’ commercial success. In real scenarios, it is possible to compare
a large number of models by using offline metrics. However, to avoid
compromising the system’s accuracy, only a limited number of models can be
examined online. Our first step is to investigate which offline evaluation
criteria enables to navigate towards architectures and parametrizations with
better online performance. More specifically, we are interested in verifying
whether a model with the highest Recall@$k$ (when evaluated offline) also
produces the highest CTR (when evaluated online). We also verified the impact
of including popularity-penalization and time aspect on the CTR-Recall@$k$
relation. Finally, we introduce a new offline evaluation metric more adaptive
to live environments. Our metric, so-called $recall@K_{LLOO}^{\beta}$,
simultaneously incorporates popularity penalization and time dependency of
interactions.

##  2 Related work

Due to the complexity of performing online evaluations, comparative studies
between online and offline metrics are scarce. Added to that, existing
solutions typically analyze a single dataset. For instance, in [25] the
authors compare offline and online metrics on the Swiss news website
swissinfo.ch. They constructed a metric titled Success@$k$ and used it to fit
the model. The value of Success@$k$ in the (offline) validation set is then
compared to the CTR in the online environment. As a result, they hypothesize
that RAs that are dominant based on offline metrics are no longer as effective
in the online context since they favor popular items. In contrast, the RA that
recommends random items does significantly better in the online evaluation
than in the offline evaluation because they encourage content exploration. As
a follow-up, in [26] they proposed a model predicting online performance based
on five different offline metrics but did not find a universal formula for
predicting online performance. A similar mismatch between offline and online
evaluation is shown for individual domains. For example, in [27], the authors
used the MovieLens dataset and evaluated the online performance of RA based on
feedback from 100 users invited to their experiment. The behavior of Docear
users receiving recommendations of research articles was investigated in [28,
19] with the conclusion that offline evaluations are probably not suitable to
evaluate recommender systems in this domain. An experiment involving 4287
users of a travel agency was conducted in [29]. However, according to the
findings reported in [30], a general cross-domain comparison is missing. A
study from Netflix [31] from 2021 describes the same issue regarding deep-
learning models. They identify a "mismatch in offline and online settings" as
one of the unresolved practical challenges of current recommendation systems.
The authors of the study give a hint that Netflix uses its own offline bias-
suppressing metric for more corresponding offline evaluation. However, they
failed to describe essential details, such as how to use contextual bandit
techniques to remove various biases. The researchers in [32] addressed the
challenge of offline evaluation in industry recommender systems by
investigating behavioral principles and developing RecList, an open-source
tool that employs NLP techniques to assess the effectiveness of a RA in common
recommendation scenarios. All of the previously referenced research compare
offline to online metrics without taking popularity bias and time-dependence
into account. Differently, we investigate how a correction for popularity bias
[13] and a validation set consisting purely of interactions that happened
after the end of the training data [21] affect the optimization of online
metrics. We also analyzed multiple datasets.

###  2.1 Contributions

The main contributions of this paper are listed as follows:

  * •

We introduced a new offline evaluation criterion that included both (1)
popularity penalization and (2) time aspect of interactions
($recall@K_{LLOO}^{\beta}$, see Section 3.1).

  * •

We conducted a large-scale experiment on real-world datasets that shows our
criterion has an advantage in predicting online performance over the popular
criteria like recall@N used in the RecSys community.

##  3 Method

In our experiment, we are examining whether (1) incorporating a time dimension
into an offline evaluation approach, and (2) reducing popularity bias by
assigning less weight to errors of frequently interacted items, reduces the
disparity between offline and online metrics. In theory, one expects that
offline metrics (when employed to cross-validate models) result in improved
online performance in live environments.

Basic notation: Denote the set of interactions between users and items by
$F=\\{f_{1},\dots,f_{p}\\}$. A single interaction is denoted as
$f_{j}\in(U\times I\times\mathbb{Z}_{t})\text{ for }\forall
j\in\\{1,\dots,p\\}$, where $U=\\{u_{1},\dots,u_{m}\\}$ is a set of all RS
users, $I=\\{i_{1},\dots,i_{n}\\}$ is a set of items which can be recommended,
$\mathbb{Z}_{t}$ is the set of integers expressing the timestamp when the
interaction was performed and $p$ is a total number of interactions. Then we
represent the set of interactions between the item $i$ and the user $u$ as

$F_{u,i}=\\{(u_{j},i_{j},t_{j})\mid(u_{j},i_{j},t_{j})\in F:u_{j}=u\land
i_{j}=i\\}.$

Finally, define the set of relevant items for the user $u$ as $N_{u}\subset
I$. We assume that items that are relevant for a given user can be extracted
from explicit and/or implicit feedback. Thus, we considered the item $i$
relevant to the user $u$ if $u$ implicitly (e.g., view, click) interacted with
$i$.

###  3.1 Offline metrics

We will first present offline metrics, which will then be compared to online
measurements. Regarding the cross-validating split procedure, we are
considering LOOCV and LLOOCV. The most common way to compute recall measured
using LOOCV is expressed by:

$recall@K_{LOO}=\frac{\sum\limits_{u\in U}\sum\limits_{i\in
N_{u}}\mid\\{i\\}\cap Top_{K}(N_{u}\setminus\\{i\\})\mid}{\sum\limits_{u\in
U}\mid N_{u}\mid},$ (1)

where $Top_{K}(M)$ is a recommendation algorithm that selects $K$ items based
on items in the set $M\subset I$ recommendable items. Conversely, recall
measured using LLOOCV can be computed by

$recall@K_{LLOO}=\frac{\sum\limits_{u\in U}\sum\limits_{(i_{1},t_{1})\in
F_{u}}\mid\\{i_{1}\\}\cap Top_{K}(Q_{t_{1}})\mid}{\sum\limits_{u\in U}\mid
N_{u}\mid},$ (2)

with

$Q_{t_{1}}=\\{i_{2}\mid(i_{2},t_{2})\in F_{u}:t_{2}<t_{1}\\}$

where $F_{u}$ is a list of interactions of user $u$ defined as
$F_{u}=\\{(i_{j},t_{j})\mid(u_{j},i_{j},t_{j})\in F:u_{j}=u\\}$ and the
expression $\\{i_{2}\mid(i_{2},t_{2})\in F_{u}:t_{2}<t_{1}\\}$ represents the
set of items that were interacted by the user $u$ before timestamp $t_{1}$.

Including popularity-penalization from [13] and incorporating it into Eq. (1),
we get

$recall@K_{LOO}^{\beta}=\sum\limits_{u\in
U}w^{\beta}(u)\frac{\sum\limits_{i\in N_{u}}\mid\\{i\\}\cap
Top_{K}(N_{u}\setminus\\{i\\})\mid\;p(i)^{-\beta}}{\sum\limits_{i\in
N_{u}}p(i)^{-\beta}}$ (3)

and Eq. (2) turns to

$recall@K_{LLOO}^{\beta}=\sum\limits_{u\in
U}w^{\beta}(u)\frac{\sum\limits_{(i_{1},t_{1})\in F_{u}}\mid\\{i_{1}\\}\cap
Top_{K}(Q_{t_{1}})\mid\;p(i)^{-\beta}}{\sum\limits_{i\in N_{u}}p(i)^{-\beta}}$
(4)

where $w^{\beta}(u)\in[0,1]$ is a weight of user $u$. The sum of weights for
all users must sum up to one, $\sum\limits_{u\in U}w^{\beta}=1$, with
suggested:

$w^{\beta}(u)=\frac{1}{\mid U\mid}\;\frac{\sum\limits_{i\in
N_{u}}p(i)^{-\beta}}{\sum\limits_{v\in U}\sum\limits_{i\in
N_{v}}p(i)^{-\beta}}$

and $p(i)\in[0,1]$ denotes relative popularity of item $i$. Note that for
$\beta=0$, Eq. (3) and (1) are equivalent, and Eq. (4) with (2) as well.

Remark: In [13], the authors explain the effect of the hyperparameter $\beta$
for offline evaluation but no longer show whether penalizing popularity makes
recall a more appropriate metric for the online environment. [21] proposed
that reducing bias by penalization of popularity $\beta$ can lead to a better
offline evaluation, but with no experimental verification.

###  3.2 Online evaluation

Another approach to evaluating a RA is based on feedback from users
interacting with a live recommender system. More specifically, we work on a
scenario where items are recommended to a user, and the RS collects the user’s
reactions to the recommended items. An example of a reaction is when the user
clicks on the recommended item.

The most widely used online metric (given its universality) is the click-
through rate (CTR). CTR can be seen as the ratio between the accepted
recommendations and all offered recommendations [28]. We consider that the
user accepted the recommendation if he clicked on at least one of the
recommended items.

Remark: A recommender system can observe implicit and explicit CTRs. An
explicit CTR is calculated if the RS has clear evidence that a user clicked on
a particular item as a result of the recommendation. The implicit CTR can be
calculated based on interactions if the RS does not have explicit knowledge
that the item has been clicked through as a result of the recommendation.

Formally, $C:Z_{t}\times U\times\\{0,1\\}^{I}$ defines a set of
recommendations where each recommendation is represented by a timestamp $t\in
Z_{t}$, user $u\in U$ and by a set of recommended items $I^{\prime}\subset I$.
When assuming that the set of interactions $F$ contains only "clicked-type"
interactions, then the implicit CTR can be calculated as:

$iCTR(d)=\frac{\sum\limits_{(t,u,I^{\prime})\in C}sgn(\mid I^{\prime}\cap
F_{u}(t,d)\mid)}{\mid C\mid},$ (5)

where $F_{u}(t,d)$ is a set of items interacted by the user $u$ within time
$[t,t+d]$ defined as

$F_{u}(t,d)=\\{i_{j}\mid(i_{j},t_{j})\in
F_{u}:(t_{j}>=t)\land(t+d>=t_{j})\\},$

and $d$ is a parameter determining how long after the recommendation the user
has to interact with the recommended item to mark the recommendation as
successful.

###  3.3 Methodology of the experiment

The goal of our experiment is to find out how different versions of
$recall@K^{\beta}_{LOO}$ and $recall@K^{\beta}_{LLOO}$ as validation metric
relates to CTR.

Due to the limited resources to conduct online experiments, to perform our
analysis, we first select a backbone algorithm: the item-$k$NN algorithm [33]
with the similarity between items measured by the cosine similarities of
latent space embeddings. The latent space embeddings are created using matrix
factorization from implicit feedback [34] with different data preprocessing
and hyperparameters (such as latent space size and regularization) to ensure
diverse performance according to offline metrics. Second, we train our model
and measure its performance using different versions of recall (i.e.,
$recall@K^{\beta}_{LOO}$ and $recall@K^{\beta}_{LLOO}$ with $\beta$ as a
hyperparameter). Third, our model is deployed to an RS with live interactions,
and thus the CTR can be measured. Note that the RS is constantly receiving new
interactions from users. Therefore, we re-trained the model to include them
periodically.

Once the individual steps of the experiment are fulfilled and implemented, the
experiment is performed on several datasets. The results of the experiment are
measured CTRs along with the number of users that interacted with each model.
The RS splits users for each model equally. Once the user was assigned to the
model during the first recommendation, the same model generated any further
recommendations.

Subsequently, the vector of CTRs can be taken for the dataset $A$ and its
$L=5$ deployed models $S^{A}=(S_{1}^{A},S_{2}^{A},\dots,S_{5}^{A})$.
Similarly, one $E^{A}=(E_{1}^{A},E_{2}^{A},\dots,E_{5}^{A})$ vector is
measured for each combination of hyperparameters $V\\!AL$, $\beta,k$. The
entire list of vectors of recalls is measured according to their
hyperparameters
$EL^{A}=\\{E^{A}_{V\\!AL_{1},\beta_{1},k_{1}},E^{A}_{V\\!AL_{2},\beta_{2},k_{2}},\dots,E^{A}_{V\\!AL_{V},\beta_{V},k_{V}}\\}$,
where $V$ is the total number of combinations of hyperparameters and
$V\\!AL_{j}$, $\beta_{j},k_{j}$ are the individual hyperparameter values.

Inspired by practical application, we are interested in whether the best model
according to offline metrics for a given dataset is also the best according to
online metrics. In other words, we find out what the chances are that if we
choose the best model according to recall, it will be the best model according
to CTR. This can be measured using Recall@$1$. To distinguish between
$recall@K^{\beta}_{LLOO}$ measuring the quality of item recommendations and
Recall@$1$ measuring whether the best model according to offline metrics is
also the best model in online evaluation, we will explicitly denote the latter
as Model Selection Recall (MSR). We define MSR as the ratio of how many times
the best model according to offline metrics has been selected by offline
metrics, namely recalls with different hyperparameters ($\beta$, $V\\!AL$).

##  4 Experiments

In this section, we will describe the used datasets and present the results of
our large-scale experiment.

###  4.1 Datasets and collected data

Commonly stable research datasets (such as MovieLens or Last.fm) cannot be
used in our experiment since live users are required for online evaluation.
Because of that, our work was performed by using real datasets with live
customers. For each model and each dataset, iCTR with a parameter $d=10$
(minutes) was measured over 18 days. The number of users and the number of
their recommendations participating in iCTR measurement depend on the data set
and other external circumstances and are shown in Table 1.

Table 1: Description of the total number of items and users in the datasets
along with the average number of users and interactions per model used to
measure iCTR

Dataset | Description | Interactions | Users | Items | Users per model | Interactions per model
---|---|---|---|---|---|---
A | Liquor e-shop | 2.8m | 1.3m | 3k | 7.0k | 22.7k
B | Pet store | 16.8m | 6.9m | 20k | 68.8k | 146.3k
C | Fashion e-shop | 30.4m | 3.1m | 19.3k | 6.3k | 19.1k
D | Supplier of African goods | 13.9m | 70k | 1k | 19.4k | 67.0k
E | Videostreaming service | 30.7m | 1.8m | 5.3k | 19.6k | 69.7k

The datasets have been selected to include different domains. In addition to
e-commerce services, a video streaming platform is represented. Also, dataset
D is very different from other e-commerce customers as it is a B2B business
with a few products and customers with an unconventional high number of
interactions. Another parameter by which the datasets were selected is the
number of recommendations per day. The datasets with small traffic could not
be selected since the traffic needs to be divided between models and an
estimate of CTR needs to be as accurate as possible.

###  4.2 Used hyperparameters and resulting MSR

The values of hyperparameters for which recall was measured were
$k\in\\{1,2,3,4,5,6,7,8,9,10,15,20,25,50\\}$ and $\beta\in\\{0.05j\mid
j\in\\{0,1,\dots,20\\}\\}$. The $V\\!AL$ hyperparameter specifies whether is
used Equation (3) or (4) for the cross-validation method. Figure 1 shows the
relation between iCTR and recall for selected $\beta$s and both values of
$V\\!AL$ hyperparameter. It can be seen that the inclusion of the time aspect
using the LLOCV technique led to an increase in MSR, which means the best
online model was more often selected using the offline metric. The same effect
can be seen when using the penalization of popularity by the beta
hyperparameter. However, it is not true that the more popularity is penalized,
the better the offline metric is.

The best metric found with LLOOCV and $\beta=0.30$ has MSR$=34.29\%$ and
therefore, it is better in choosing the best online model than commonly used
LOOCV technique with $\beta=0$ (i.e., without popularity penalization) with
MSR$=12.86\%$.

Figure 1: Including a time aspect in the evaluation using the LLOCV approach
increases the chance that the selected model will be the best online model
(measured by MSR)

##  5 Conclusion

We researched various solutions to better address the known issues of offline
metrics with the aim of reducing the gap between offline and online metrics.
Then we performed a large-scale experiment that examined the effect of
penalizing popularity and including the time aspect of recommendations on the
relation between recall and CTR. The experiment was conducted on five
commercial datasets covering multiple domains (such as e-commerce, video
streaming). It was shown that, in general, maximizing recall does not always
lead to maximizing CTR. Popularity-stratified recall proved to be a good
approach for reducing the MNAR problem leading to better model selection for
an online environment but measured using offline metrics. Offline evaluation
with an emphasis on the time aspect of recommendations using leave-last-one-
out cross-validation also showed that it can lead to an improvement in MSR.
Using the proposed method, we were able to improve the selection of the best
online model from the original MSR$=12.86\%$ to MSR$=34.29\%$.

###  5.1 Future work

The relation between recall and CTR was investigated on five datasets and each
contained five different models. To measure the relation more accurately, it
would be advisable to have more models, but this greatly prolongs the
experiment (since there is a limit traffic of new users) and increases the
already exhaustive engineering effort. Similarly, it would be interesting to
include datasets from other domains, such as news or bazaars, as these are
very specific to the changing popularity of the item. As a final improvement,
the SW-EVAL method could be used for stricter adherence to the time aspect.
Another extension advisable for the future is to examine how the best possible
offline metric relates to dataset attributes such as number of users, number
of items, sparsity of the interaction matrix, and domain of the dataset. This
requires a large meta-study based on experiments with dozens of real datasets
for a long period of time.

###### Acknowledgements.

This work was supported by the Grant Agency of the Czech Technical University
in Prague (SGS23/210/OHK3/3T/18). The experiment was carried out in
cooperation with Recombee.

## References

  * Ledent et al. [2021] A. Ledent, R. Alves, M. Kloft,  Orthogonal Inductive Matrix Completion,  IEEE Transactions on Neural Networks and Learning Systems (2021) 1–12. doi:10.1109/TNNLS.2021.3106155, arXiv:2004.01653 [cs, stat].
  * Silveira et al. [2019] T. Silveira, M. Zhang, X. Lin, Y. Liu, S. Ma,  How good your recommender system is? A survey on evaluations in recommendation,  International Journal of Machine Learning and Cybernetics 10 (2019) 813–831. doi:10.1007/s13042-017-0762-9.
  * Ni et al. [2019] J. Ni, J. Li, J. McAuley,  Justifying Recommendations using Distantly-Labeled Reviews and Fine-Grained Aspects,  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), Association for Computational Linguistics, Hong Kong, China, 2019, pp. 188–197. URL: https://www.aclweb.org/anthology/D19-1018. doi:10.18653/v1/D19-1018.
  * Wannigamage et al. [2020] D. Wannigamage, M. Barlow, E. Lakshika, K. Kasmarik,  Steam Games Dataset : Player count history, Price history and data about games,  volume 1, 2020. URL: https://data.mendeley.com/datasets/ycy3sy3vj2/1. doi:10.17632/ycy3sy3vj2.1, publisher: Mendeley Data.
  * Gunawardana et al. [2022] A. Gunawardana, G. Shani, S. Yogev, Evaluating Recommender Systems, Springer US, New York, NY, 2022, pp. 547–601. URL: https://doi.org/10.1007/978-1-0716-2197-4_15. doi:10.1007/978-1-0716-2197-4_15.
  * Wang et al. [2019] H. Wang, F. Zhang, M. Zhang, J. Leskovec, M. Zhao, W. Li, Z. Wang,  Knowledge-aware Graph Neural Networks with Label Smoothness Regularization for Recommender Systems,  in: Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD ’19, Association for Computing Machinery, New York, NY, USA, 2019, pp. 968–977. doi:10.1145/3292500.3330836.
  * Sachdeva et al. [2018] N. Sachdeva, G. Manco, E. Ritacco, V. Pudi, Sequential Variational Autoencoders for Collaborative Filtering, Technical Report arXiv:1811.09975, arXiv, 2018. ArXiv:1811.09975 [cs, stat] type: article.
  * Steck [2019] H. Steck,  Embarrassingly Shallow Autoencoders for Sparse Data,  in: The World Wide Web Conference, WWW ’19, Association for Computing Machinery, New York, NY, USA, 2019, pp. 3251–3257. doi:10.1145/3308558.3313710.
  * Yang et al. [2017] C. Yang, L. Bai, C. Zhang, Q. Yuan, J. Han,  Bridging Collaborative Filtering and Semi-Supervised Learning: A Neural Approach for POI Recommendation,  in: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’17, Association for Computing Machinery, New York, NY, USA, 2017, pp. 1245–1254. URL: https://doi.org/10.1145/3097983.3098094. doi:10.1145/3097983.3098094.
  * Tay et al. [2018] Y. Tay, L. Anh Tuan, S. C. Hui,  Latent Relational Metric Learning via Memory-based Attention for Collaborative Ranking,  in: Proceedings of the 2018 World Wide Web Conference, WWW ’18, International World Wide Web Conferences Steering Committee, Republic and Canton of Geneva, CHE, 2018, pp. 729–739. doi:10.1145/3178876.3186154.
  * Marlin et al. [2007] B. M. Marlin, R. S. Zemel, S. Roweis, M. Slaney,  Collaborative filtering and the missing at random assumption,  in: Proceedings of the Twenty-Third Conference on Uncertainty in Artificial Intelligence, UAI’07, AUAI Press, Arlington, Virginia, USA, 2007, pp. 267–275.
  * Marlin and Zemel [2009] B. M. Marlin, R. S. Zemel,  Collaborative prediction and ranking with non-random missing data,  in: Proceedings of the third ACM conference on Recommender systems, RecSys ’09, Association for Computing Machinery, New York, NY, USA, 2009, pp. 5–12. doi:10.1145/1639714.1639717.
  * Steck [2011] H. Steck,  Item popularity and recommendation accuracy,  in: Proceedings of the fifth ACM conference on Recommender systems, RecSys ’11, Association for Computing Machinery, New York, NY, USA, 2011, pp. 125–132. doi:10.1145/2043932.2043957.
  * Li and She [2017] X. Li, J. She,  Collaborative Variational Autoencoder for Recommender Systems,  in: Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, Halifax NS Canada, 2017, pp. 305–314. doi:10.1145/3097983.3098077.
  * Vinagre et al. [2014] J. Vinagre, A. M. Jorge, J. Gama,  Evaluation of recommender systems in streaming environments,  Silicon Valley, United States, 2014\. doi:10.13140/2.1.4381.5367, arXiv:1504.08175 [cs].
  * Carraro and Bridge [2022] D. Carraro, D. Bridge,  A sampling approach to Debiasing the offline evaluation of recommender systems,  Journal of Intelligent Information Systems 58 (2022) 311–336. URL: https://link.springer.com/10.1007/s10844-021-00651-y. doi:10.1007/s10844-021-00651-y.
  * Carraro and Bridge [2020] D. Carraro, D. Bridge,  Debiased offline evaluation of recommender systems: a weighted-sampling approach,  in: Proceedings of the 35th Annual ACM Symposium on Applied Computing, SAC ’20, Association for Computing Machinery, New York, NY, USA, 2020, pp. 1435–1442. URL: https://doi.org/10.1145/3341105.3375759. doi:10.1145/3341105.3375759.
  * Li et al. [2011] L. Li, W. Chu, J. Langford, X. Wang,  Unbiased offline evaluation of contextual-bandit-based news article recommendation algorithms,  in: Proceedings of the Fourth ACM International Conference on Web Search and Data Mining, WSDM ’11, Association for Computing Machinery, New York, NY, USA, 2011, p. 297–306. URL: https://doi.org/10.1145/1935826.1935878. doi:10.1145/1935826.1935878.
  * Beel and Langer [2015] J. Beel, S. Langer,  A comparison of offline evaluations, online evaluations, and user studies in the context of research-paper recommender systems,  in: S. Kapidakis, C. Mazurek, M. Werla (Eds.), Research and Advanced Technology for Digital Libraries, Springer International Publishing, Cham, 2015, pp. 153–168.
  * Zhao et al. [2018] Q. Zhao, J. Chen, M. Chen, S. Jain, A. Beutel, F. Belletti, E. H. Chi,  Categorical-attributes-based item classification for recommender systems,  in: Proceedings of the 12th ACM Conference on Recommender Systems, RecSys ’18, Association for Computing Machinery, New York, NY, USA, 2018, pp. 320–328. doi:10.1145/3240323.3240367.
  * Jeunen et al. [2018] O. Jeunen, K. Verstrepen, B. Goethals,  Fair Offline Evaluation Methodologies for Implicit-Feedback Recommender Systems with MNAR Data,  Vancouver, Canada, 2018, p. 8. URL: http://adrem.uantwerpen.be/bibrem/pubs/OfflineEvalJeunen2018.pdf.
  * Řehořek [2019] T. Řehořek, Manipulating the Capacity of Recommendation Models in Recall-Coverage Optimization, Ph.D. thesis, Czech Technical University, 2019. URL: https://dspace.cvut.cz/handle/10467/81823, accepted: 2019-04-05T11:19:10Z Publisher: České vysoké učení technické v Praze. Vypočetní a informační centrum.
  * Cañamares et al. [2020] R. Cañamares, P. Castells, A. Moffat,  Offline evaluation options for recommender systems,  Information Retrieval Journal 23 (2020) 387–410. doi:10.1007/s10791-020-09371-3.
  * Bianchi et al. [2023] F. Bianchi, P. J. Chia, C. Greco, C. Pomo, G. Moreira, D. Eynard, F. Husain, J. Tagliabue, Evalrs 2023. well-rounded recommender systems for real-world deployments, 2023. arXiv:2304.07145.
  * Garcin et al. [2014] F. Garcin, B. Faltings, O. Donatsch, A. Alazzawi, C. Bruttin, A. Huber,  Offline and online evaluation of news recommender systems at swissinfo.ch,  in: Proceedings of the 8th ACM Conference on Recommender systems - RecSys ’14, ACM Press, Foster City, Silicon Valley, California, USA, 2014, pp. 169–176. doi:10.1145/2645710.2645745.
  * Maksai et al. [2015] A. Maksai, F. Garcin, B. Faltings,  Predicting online performance of news recommender systems through richer evaluation metrics,  in: Proceedings of the 9th ACM Conference on Recommender Systems, RecSys ’15, Association for Computing Machinery, New York, NY, USA, 2015, p. 179–186. URL: https://doi.org/10.1145/2792838.2800184. doi:10.1145/2792838.2800184.
  * Rossetti et al. [2016] M. Rossetti, F. Stella, M. Zanker,  Contrasting Offline and Online Results when Evaluating Recommendation Algorithms,  in: Proceedings of the 10th ACM Conference on Recommender Systems, RecSys ’16, Association for Computing Machinery, New York, NY, USA, 2016, pp. 31–34. URL: https://doi.org/10.1145/2959100.2959176. doi:10.1145/2959100.2959176.
  * Beel et al. [2013] J. Beel, M. Genzmehr, S. Langer, A. Nürnberger, B. Gipp,  A comparative analysis of offline and online evaluations and discussion of research paper recommender system evaluation,  in: Proceedings of the International Workshop on Reproducibility and Replication in Recommender Systems Evaluation, RepSys ’13, Association for Computing Machinery, New York, NY, USA, 2013, pp. 7–14. doi:10.1145/2532508.2532511.
  * Peska and Vojtas [2020] L. Peska, P. Vojtas,  Off-line vs. On-line Evaluation of Recommender Systems in Small E-commerce,  Proceedings of the 31st ACM Conference on Hypertext and Social Media (2020) 291–300. doi:10.1145/3372923.3404781, arXiv: 1809.03186.
  * Jeunen [2019] O. Jeunen,  Revisiting offline evaluation for implicit-feedback recommender systems,  in: Proceedings of the 13th ACM Conference on Recommender Systems, RecSys ’19, Association for Computing Machinery, New York, NY, USA, 2019, pp. 596–600. doi:10.1145/3298689.3347069.
  * Steck et al. [2021] H. Steck, L. Baltrunas, E. Elahi, D. Liang, Y. Raimond, J. Basilico,  Deep Learning for Recommender Systems: A Netflix Case Study,  AI Magazine 42 (2021) 7–18. URL: https://ojs.aaai.org/index.php/aimagazine/article/view/18140. doi:10.1609/aimag.v42i3.18140, number: 3.
  * Chia et al. [2022] P. J. Chia, J. Tagliabue, F. Bianchi, C. He, B. Ko,  Beyond ndcg: Behavioral testing of recommender systems with reclist,  WWW ’22 Companion, Association for Computing Machinery, New York, NY, USA, 2022, p. 99–104. URL: https://doi.org/10.1145/3487553.3524215. doi:10.1145/3487553.3524215.
  * Nikolakopoulos et al. [2022] A. N. Nikolakopoulos, X. Ning, C. Desrosiers, G. Karypis,  Trust Your Neighbors: A Comprehensive Survey of Neighborhood-Based Methods for Recommender Systems,  in: F. Ricci, L. Rokach, B. Shapira (Eds.), Recommender Systems Handbook, Springer US, New York, NY, 2022, pp. 39–89. URL: https://doi.org/10.1007/978-1-0716-2197-4_2. doi:10.1007/978-1-0716-2197-4_2.
  * Hu et al. [2008] Y. Hu, Y. Koren, C. Volinsky,  Collaborative Filtering for Implicit Feedback Datasets,  2008, pp. 263–272. doi:10.1109/ICDM.2008.22.


#  Simulating Hamiltonian dynamics in a programmable photonic quantum
processor using linear combinations of unitary operations

Yue Yu1,⋆ Yulin Chi1,⋆ Chonghao Zhai1 Jieshan Huang1 Qihuang Gong1,2,3,4,5
Jianwei Wang1,2,3,4,5,†

1 State Key Laboratory for Mesoscopic Physics, School of Physics, Peking
University, Beijing, 100871, China
2 Frontiers Science Center for Nano-optoelectronics & Collaborative Innovation
Center of Quantum Matter, Peking University, Beijing, 100871, China
3 Collaborative Innovation Center of Extreme Optics, Shanxi University,
Taiyuan 030006, Shanxi, China
4 Peking University Yangtze Delta Institute of Optoelectronics, Nantong
226010, Jiangsu, China.
5 Hefei National Laboratory, Hefei 230088, China
$\star$ These authors contributed equally to this work. $\dagger$ emails to:
<EMAIL_ADDRESS>
> Simulating the dynamic evolutions of physical and molecular systems in a
> quantum computer is of fundamental interest in many applications [1, 2]. Its
> implementation requires efficient quantum simulation algorithms [3, 4, 5, 6,
> 7, 8, 9, 10, 11, 12]. The Lie-Trotter-Suzuki approximation algorithm, also
> well known as the Trotterization, is a basic algorithm in quantum dynamic
> simulation[3, 4, 5]. A multi-product algorithm that is a linear combination
> of multiple Trotterizations has been proposed to improve the approximation
> accuracy [13]. Implementing such multi-product Trotterization in quantum
> computers however remains experimentally challenging and its success
> probability is limited. Here, we modify the multi-product Trotterization and
> combine it with the oblivious amplitude amplification to simultaneously
> reach a high simulation precision and high success probability. We
> experimentally implement the modified multi-product algorithm in an
> integrated-photonics programmable quantum simulator in silicon, which allows
> the initialization, manipulation and measurement of four-qubit states and a
> sequence of linearly combined controlled-unitary gates, to emulate the
> dynamics of a coupled electron and nuclear spins system. Theoretical and
> experimental results are in good agreement, and they both show the modified
> multi-product algorithm can simulate Hamiltonian dynamics with a higher
> precision than conventional Trotterizations and a nearly deterministic
> success probability. We certificate the multi-product algorithm in a small-
> scale quantum simulator based on linear combinations of operations, and this
> work promises the practical implementations of quantum dynamics simulations.

Efficiently simulating the quantum dynamics of physical and molecular systems
represents an important near-term application of quantum computers [1, 2].
Several quantum algorithms have been proposed for simulating quantum
Hamiltonian dynamics, e.g., Lie-Trotter-Suzuki approximations [3, 4, 5] (known
as Trotterizations), quantum random walks [14, 15], multi-product formula
[13], truncated Taylor series [7, 8], qubitization [9] and quantum signal
processing [10]. Among them, Trotterization is regarded as a basic algorithm
in dynamics simulations. The Trotterization accuracy however appears to be
orders of magnitude looser than its prediction error bounded by numerical
simulations [16, 17]. Many algorithms have been proposed to improve the
Trotterizations, e.g, product order randomization [11], time-dependent
Hamiltonian simulation [12], and truncated Taylor series [7, 8]. The order of
Lie-Trotter-Suzuki approximation determines the error of Trotterization. For
example, the first-order formula requires a $\mathcal{O}(t^{2}/\epsilon)$-step
Trotterization with an error of $\epsilon$. Expectably, utilizing higher-order
formula can result in a substantial improvement of precision at the expense of
more quantum operations and higher circuit depth [18, 19]. Another efficient
multi-product algorithm was proposed by Childs and Wiebe [13], which can reach
the same precision as the high-order Trotterization but with a lower circuit
depth.

The quantum hardware for implementing the multi-product algorithm is a linear
combinations of unitaries (LCU)[13]. Note the LCU enables a general form of
quantum operations that can be used to implement Hamiltonian simulation[13,
7], Harrow-Hassidim-Lloyd algorithm[20], passive quantum error correction[21]
and simulation of the Yang-Baxter equation[22]. The realization of LCU
circuits in quantum devices requires the implementation of a sequence of
multi-qubit controlled-unitary operations [23]. Realizing such multi-qubit
controlled-unitary operations, in which the unitary can be arbitrarily
controllable, is generally a challenging task, though multi-qubit gates have
been reported in different quantum systems, e.g, superconducting qubits [24],
trapped ions [25] and photons [26]. In photonic systems, controlled-unitary
operations between qubits or qudits have been demonstrated [27, 28, 29, 30,
31]. Silicon-photonics quantum technologies [32], that can integrate
entangled-photon sources [33], programmable quantum circuits [34, 35], and
single-photon detectors [36], could provide a versatile platform for multi-
qubit LCU-based Hamiltonian dynamics simulation.

Here, we propose and demonstrate a modified multi-product algorithm, assisted
by the oblivious amplitude amplification (OAA). The modified multi-product
algorithm allows a higher accuracy of dynamics simulation compared to
conventional Trotterizations as well as the original multi-product [13], and
it also enables a nearly deterministic success probability. We experimentally
implement our modified multi-product algorithms in a LCU quantum simulator on
a programmable four-qubit quantum photonic chip. To benchmark the processing
of the modified multi-product algorithm, we simulate a general Rabi-type
Hamiltonian of a coupled nuclear spin and electron spin system. To the best of
our knowledge, this work reports the first multi-qubit controlled-unitary gate
in integrated photonics, and we reprogram the device to implement the first
Hamiltonian dynamics simulation in LCU circuits.

Figure 1: Architecture of quantum dynamics simulation using the modified
multi-product algorithms with OAA in linearly-combined unitary circuits.
Multi-product algorithms (yellow boxed) can linearly combine multiple low-
order Trotterizations ($\mathcal{S}_{1}^{l}$) to improve the simulation
accuracy of quantum dynamics. The LCU circuits (blue boxed) represent the
quantum hardware that can implement the multi-product algorithms, and the LCU
can be physically realized by a sequence of quantum controlled-unitary
operations. There are many failing outcomes in the conventional LCU
algorithms, resulting in a low probability of success. We adopt the OAA method
(green boxed) to amplify the success probability of the algorithm. This
architecture allows enhanced multi-product algorithms for quantum simulation
of dynamic evolution, with an improved accuracy and a high success
probability. By properly choosing the coefficients $c_{i}$, iteration numbers
$L(i)$ and $N$ so that $\sin^{2}[(2N+1)\arcsin\sqrt{P}]=1$, we can amplify the
success probability up to unit.

### Multi-product algorithms in LCU circuits

We first overview the original multi-product algorithm [13], and then discuss
how to improve it with an assistance of the OAA algorithm [8]. When
considering the second-order Trotter approximation of a unitary operator of
$\exp(-i\sum_{j=1}^{m}\mathcal{H}_{j}t)$ given $\exp(-i\mathcal{H}_{j}t)$, we
have:

$\displaystyle\begin{split}e^{-i\sum_{j=1}^{m}\mathcal{H}_{j}t}&=\mathcal{S}_{1}^{l}(t/l)+E_{3}t^{3}/l^{2}+E_{5}t^{5}/l^{4}+\cdots,\\\
\mathcal{S}_{1}(t)&=\prod_{j=1}^{m}e^{-i\mathcal{H}_{j}t/2}\prod_{k=m}^{1}e^{-i\mathcal{H}_{k}t/2}\end{split}$
(1)

where $\mathcal{S}_{1}(t)$ is the second-order Trotter product, $E_{3}$ and
$E_{5}$ are high-order error terms which are functions of $\mathcal{H}_{j}$,
$t$ is the evolution time of the quantum system, and $l$ is the number of
iterations. Simply increasing the $l$, one can reduce the high-order errors
but cannot get rid of them. The key idea of the multi-product algorithm is to
properly combine multiple low-order Trotterizations linearly, so that the low-
order error terms can be cancelled. For example, by properly choosing the
coefficients of $c_{n}={n^{2}}/({n^{2}-m^{2}})$ and
$c_{m}={m^{2}}/({m^{2}-n^{2}})$, and linearly combining two second-order
Trotterizations with $n$ and $m$ iterations respectively, one can directly
cancel the third-order error term $E_{3}$ and thus improve the approximation
to the fifth-order error:

$\displaystyle
e^{-i\sum_{j=1}^{m}\mathcal{H}_{j}t}=c_{n}\mathcal{S}_{1}^{n}(t/n)+c_{m}\mathcal{S}_{1}^{m}(t/m)-E_{5}t^{5}/n^{2}m^{2}+\mathcal{O}(t^{7})$
(2)

That being said, the error of quantum dynamics simulation grows in
$\mathcal{O}(t^{5})$ by a linear combination of two Trotterizations.
Experimentally, this could be realised using a LCU of two second-order
Trotterizations. In general, one can repeat the procedure and reach an error
of $\mathcal{O}(t^{2k+1})$ by the LCU of $k$ second-order Trotterizations with
a proper choice of their coefficients [37]:

$\displaystyle\begin{split}e^{-i\sum_{j=1}^{m}\mathcal{H}_{j}t}=&\sum_{q=1}^{k}c_{q}\mathcal{S}_{1}^{L(q)}(t/L(q))+\\\
&(-1)^{k-1}E_{2k+1}t^{2k+1}\prod_{q=1}^{k}\frac{1}{L^{2}(q)}+\mathcal{O}(t^{2k+3}),\end{split}$
(3)

where $c_{q}$ are chosen as $\prod_{p\neq
q,p=1}^{k}[{L^{2}(q)}/({L^{2}(q)-L^{2}(p)})]$, the $c_{q}$ satisfy
$\sum_{q=1}^{k}c_{q}=1$, and $L(q)$ is the number of iteration for the $q$-th
second-order formula (without loss of generality, we assume $L(q)$ is a
monotonically increasing function).

Fig.1 illustrates the scheme of multi-product algorithm, where $A_{i}$
represents $c_{i}S_{1}^{L(i)}$ ($i=1,2,\cdots,N$) in Eq.(3), and its physical
implementation in LCU circuits. The LCU circuits can be realized with a
sequence of quantum controlled-unitary operations [23], as shown in Fig.2a.
Implementing the multi-product algorithm in the LCU circuits can significantly
improve the Trotterization precision.

While obtaining the required linear combination of
$B_{1}=\sum_{i=1}^{N}A_{i}$, the LCU circuits will also return the results of
other linear combination terms ($B_{2}$,…,$B_{N}$) that should be in spam.
These unwanted combinations are caused by the entanglement between ancillary
and data register, and will result in a low success probability of the LCU
circuits (see more details in Supplementary Information). The success
probability drops quickly as the number of combined unitary gate grows. This
is because $c_{q}$ and $c_{q+1}$ are different in sign, which makes the
success probability of $\text{Pr}=1/(\sum_{q=1}^{k}|c_{q}|)^{2}$ less than the
unit. To overcome this, one can design the function $L(q)$ to meet
$\sum_{q=1}^{k}|c_{q}|\approx 1$ to improve the probability. However, there is
a trade-off between high success probability ($\sum_{q=1}^{k}|c_{q}|\approx
1$) and low algorithm error ($\sum_{q=1}^{k}c_{q}=1$) in original multi-
product algorithm, making it impossible to target for both of them. It is this
trade-off that reduces multi-product algorithm’s potential in precision.

Figure 2: A programmable LCU quantum simulator in a silicon nanophotonic chip.
a, Quantum circuit for a four-qubit LCU circuit. The top two qubits refer to
an ancillary register initialized in $\ket{00}$ state, and the bottom two
qubits refer to a data register prepared in $\ket{\psi}$ state. The LCU is
enabled by a sequence of quantum controlled-unitaries.
{$A_{1},A_{2},A_{3},A_{4}$} are arbitrary two-qubit unitaries, in which the
target Hamiltonian is loaded in. For $C$ $(C^{T})$, its $i$-th element in the
first column (row) is given by $({c_{i}/\sum_{q=1}^{k}|c_{q}|})^{1/2}$. b, OAA
quantum circuit. The $W$ represents the LCU circuit described in a, and $R$
can flip the amplitude of basis $\ket{00}$ in the ancillary register. The
bracketed circuit is repeated for $N$ times to amplify the successful
probability of the LCU-based quantum algorithms, when reading out outcomes by
measuring the ancillary register in the $\ket{00}$ basis. c and d, modularized
scheme of the LCU quantum simulator. The simulator can implement the LCU
circuit in a, and can be fully reprogrammed and reconfigured to implement the
quantum algorithms. Inset: photograph of a LCU quantum simulator in a silicon
chip.  Figure 3: Theoretical analysis of different Trotterization algorithms.
We compare the simulation error between the standard Trotter formula, multi-
product and modified multi-product algorithms. The simulation error is defined
as $\left\|\ket{\psi_{\text{0}}}-\ket{\psi^{\prime}}\right\|$, where
$\ket{\psi_{0}}$ is the exact state and $\ket{\psi^{\prime}}$ refers to the
output state of quantum algorithms. In the analysis, we consider a Hamiltonian
(Eq.14) that describes the interaction of an electron spin and a nuclear spin
with initial state $\sqrt{0.3}\ket{00}+\sqrt{0.7}\ket{01}$. The iteration
number ($l$) of Trotter formula, original and modified multi-product
algorithms are $96,\\{1,2,3,96\\}$ and $\\{4,8,16,32\\}$, respectively. Note
that the additional circuit depth and error of OAA have been taken into
consideration.

We propose a modified multi-product algorithm, that is assisted by OAA, as
shown in Fig.1. The OAA algorithm can amplify the LCU success probability to
near unit in a very similar way to Grover algorithm. The quantum circuit of
OAA is plotted in Fig.2b. The OAA is enabled by implementing a
$U_{\text{OAA}}$ = $(-WRW^{\dagger}R)^{N}W$ circuit on the $\ket{0}\ket{\psi}$
state, where $W$ operator represents the LCU circuit, $R$ is the amplitude
flip operator defined as ($(I-2\ket{0}\bra{0})\otimes I$), and $N$ refers to
the number of amplification iteration. When operating a single $W$ operator on
the state, we have:

$\displaystyle
W\ket{0}\ket{\psi}=\sin\theta\ket{0}U\ket{\psi}+\cos\theta\ket{\Phi^{\perp}},$
(4)

where the operator $U$ is the target operator of LCU, $\theta$ indicates the
complex amplitude of expected state, and $(\ket{0}\bra{0}\otimes
I)\ket{\Phi^{\perp}}=0$. If we project this state with projector
$\ket{0}\bra{0}\otimes I$, it will turn into a typical LCU algorithm with
success probability of $\sin^{2}(\theta)$. When operating the OAA operator on
the state, given the $U$ is unitary, the OAA circuit will amplify $\theta$ and
return the output state as:

$\displaystyle
U_{\text{OAA}}\ket{0}\ket{\psi}=\sin[(2N+1)\theta]\ket{0}U\ket{\psi}+\cos[(2N+1)\theta]\ket{\Phi^{\perp}}$
(5)

This process is very similar to Grover algorithm. By doing this, the OAA
circuit can thus enhance the success probability from $P$ to
$\sin^{2}[(2N+1)\arcsin(\sqrt{P})]$ (see more details about OAA’s
amplification effect in Supplementary Information). Obviously, OAA circuit
requires larger circuit resource compared with LCU. In fact, it requires
$\mathcal{O}((2N+1)\chi)$ resources, where $\mathcal{O}(\chi)$ is the resource
for LCU.

One notice that, if the LCU circuit returns a unitary operator with a success
probability of $25\%$, the OAA can amplify the probability to $100\%$ with
$N=1$; if the LCU returns a non-unitary and its success probability is not
exactly $25\%$, the OAA can also allow an efficient amplification [7]. To
certificate the observation, we take an example of multi-product algorithm
with $L(q)=2^{q}$. In this case, the $\sum_{q=1}^{k}|c_{q}|$ quickly converges
to 1.969 as $k$ increases (e.g., $\sum_{q=1}^{7}|c_{q}|\approx 1.969$), which
results in $P\approx 25.79\%$. Having OAA, it allows a fast amplification of
the success probability to be $99.96\%$. Note that any $L(q)\propto c^{q}$
yields the same $c_{q}$, therefore the success probability of $L(q)=a\cdot
2^{q}$ ($a$ is a positive integer that can be chosen arbitrarily) can also be
amplified to nearly $100\%$.

Given by Eq.(3), we choose $L(q)=a\cdot 2^{q}$, and amplify the output of LCU
with OAA ($N=1$). This choice of $L(q)$ corresponds to LCU success probability
$\approx 25\%$, OAA can thus amplify it to about $100\%$. Taking the non-
unitary effect of LCU into account, we can both achieve an error of:

$\displaystyle\left\|\ket{\psi_{\text{0}}}-\ket{\psi^{\prime}}\right\|\leq\left\|E_{2k+1}\right\|\frac{t^{2k+1}}{a^{2k}2^{k^{2}+k-1}}$
(6)

which scales much slower than original multi-product algorithm as $k$ grows
($\ket{\psi_{0}}$ and $\ket{\psi^{\prime}}$ are the exact state and the output
state of algorithms, respectively, $k$ is the number of combined unitary gates
and $\left\|\cdot\right\|$ denotes the L2 norm for vector and spectral norm
for matrix) and a nearly deterministic success probability. See more details
about the derivation in Supplementary Information.

In order to demonstrate modified multi-product algorithm’s improvement in
precision compared with original multi-product algorithm and Trotterization in
a more intuitive way, we plot the corresponding simulation error in Fig.3. We
choose $L(q)=2\cdot 2^{q},q\in\\{1,2,3,4\\}$ for modified multi-product
algorithm, $L(q)=1,2,3,96$ for original multi-product algorithm and $l=96$ for
Trotterization to make them have similar circuit depths. This precision
improvement will be more significant when we combine more unitary operators in
algorithm.

### A programmable LCU-based photonic quantum simulator.

Figures 2c and 2d illustrate the schematic of a programmable four-qubit
silicon-photonic quantum simulator for the implementation , and a photograph
for the simulator is shown in the inset of Fig.2c. We implement the on-chip
mapping of quantum dit (qudit) states[30] into multiple quantum bit (qubit)
states. This allows us to implement high-fidelity and arbitrary entangling
operations between the qubits, which are key to the implementation of LCU-
based quantum algorithms.

We now discuss how to implement the LCU circuit in the quantum simulator. As
shown in Fig.2a, the LCU circuit is enabled by a sequence of programmable CCU
gates. The photonic quantum simulator in Fig.2d integrates several key
functional modules, including arbitrary local single-qubit preparation,
quantum controlled-controlled unitary operation (CCU), and local projective
measurement. The quantum simulator monolithically integrates 451 optical
components, and it was fabricated on the Silicon-on-Insulator platform using
complementary metal-oxide-semiconductor (CMOS) processes. Fabrication details
are provided in Supplementary Information.

We map quantum dit (qudit) states into multiple quantum bit (qubit) states.
For example, in our photonic chip, we have the following mapping:

$\left\\{\begin{aligned}
&\ket{0}_{\text{qudit}}\leftrightarrow\ket{00}_{\text{qubit}},~{}~{}\ket{1}_{\text{qudit}}\leftrightarrow\ket{01}_{\text{qubit}},\\\
&\ket{2}_{\text{qudit}}\leftrightarrow\ket{10}_{\text{qubit}},~{}~{}\ket{3}_{\text{qudit}}\leftrightarrow\ket{11}_{\text{qubit}}.~{}~{}\end{aligned}\right.$
(7)

In this work, the notation of $\ket{0}$, $\ket{1}$ refers to the qubit
representation.

As shown in Fig.2d, a pair of single photons are created in integrated
spontaneous four-wave mixing (SFWM) sources. By coherently pumping four
sources and by wavelength demultiplexing, it returns a four-dimensional Bell
state [34]. Using the mapping in Eq.(7), we rewrite it as a four-qubit
entangled state:

$\left(\ket{0000}+\ket{0101}+\ket{1010}+\ket{1111}\right)/2,$ (8)

where {$\ket{0},\ket{1}$} represent the logical basis of each qubit. The basic
idea is to coherently translate the entanglement in the source module to the
CCU entangling gates [27, 28, 29].

Firstly, we apply the space expansion procedure to create a six qubit
entangled state:

$\frac{1}{2}\left(\ket{00}\ket{00,\psi}+\ket{01}\ket{01,\psi}+\ket{10}\ket{10,\psi}+\ket{11}\ket{11,\psi}\right),$
(9)

where the first two qubits represent the ancillary-register states, and the
two-qubit state $\ket{\psi}$ represents the data-register and it can be
arbitrarily initialized by module 3. The $\ket{ij,\psi}$ ($i,j=0,1$) denotes
the state $\ket{\psi}$ encoded in the $(i,j)$-th layer qubits (will be erased
eventually) that are entangled with the ancillary-register qubits.

Secondly, we implement local operations $\\{A_{1},A_{2},A_{3},A_{4}\\}$ on the
$\ket{\psi}$, where $A$ represents two-qubit unitary realised by module 2. We
obtain a state of:

$\begin{split}\frac{1}{2}(&\ket{00}A_{1}\ket{00,\psi}+\ket{01}A_{2}\ket{01,\psi}+\\\
&\ket{10}A_{3}\ket{10,\psi}+\ket{11}A_{4}\ket{11,\psi}).\end{split}$ (10)

Thirdly, we implement projective measurement $M$ (module 4) on the qubits of
ancillary-register, and post-select its $\ket{00}\bra{00}$ outcomes. This
process projects the data-register into an output of

$m_{1}A_{1}\ket{00,\psi}+m_{2}A_{2}\ket{01,\psi}+m_{3}A_{3}\ket{10,\psi}+m_{4}A_{4}\ket{11,\psi},$
(11)

where {$m_{1},m_{2},m_{3},m_{4}$} correspond to the first column of the $C$
operator in Fig.2a.

Figure 4: Emulating quantum dynamics in a LCU quantum simulator. a, A
comparison of standard Trotterization, multi-product and the modified multi-
product algorithm, in term of their simulation accuracy. In the data register,
an initial state $\ket{01}$ is input into the simulator, and dynamics for the
state of $\ket{11}$ is measured. b, Simulated error for different algorithms.
Error is defined as the discrepancy of exact solution and computed results.
Quantum dynamic evolution of four different states. Points denote experimental
data, and lines refer to theoretical predictions. Both theoretical prediction
and experiment show that the modified multi-product algorithm can achieve
higher precision than the Trotterization and multi-product algorithm, when
$t\leq 30$. Error bars ($\pm 1\sigma$) are estimated from the photon
Poissonian statistics.

Finally, the coherent compression modules (modules 5,6) implements the
$C^{\prime}$ operator, as well as the projector of $\ket{00}_{p}\bra{00}$
acting on the layer qubits $\ket{ij}$ in $\ket{ij,\psi}$. Then the output
state is given as:

$\displaystyle\begin{split}&m_{1}\ket{00}_{p}\bra{00}C^{\prime}A_{1}\ket{00,\psi}+m_{2}\ket{00}_{p}\bra{00}C^{\prime}A_{2}\ket{01,\psi}+\\\
&m_{3}\ket{00}_{p}\bra{00}C^{\prime}A_{3}\ket{10,\psi}+m_{4}\ket{00}_{p}\bra{00}C^{\prime}A_{4}\ket{11,\psi},\end{split}$
(12)

where the unitaries $\\{C^{\prime},A_{1},A_{2},A_{3},A_{4}\\}$ and complex
numbers $\\{m_{1},m_{2},m_{3},m_{4}\\}$ can be arbitrarily controlled and
reprogrammed. The above post-selection only takes account of the elements in
the first row of the matrix representation of gate $C^{\prime}$. Similar
procedures can be applied to other projective post-selections.

Figure 5: Experimental results of modified multi-product algorithms with and
without OAA. a-d, Quantum dynamics of four states
{$\ket{00},\ket{01},\ket{10},\ket{11}$}, simulated using the modified multi-
product algorithm without the OAA. e-h, Quantum dynamics of four states
{$\ket{00},\ket{01},\ket{10},\ket{11}$}, simulated using the modified multi-
product algorithm with the OAA. i, Measured success probability for the
modified multi-product algorithm with OAA ($99.79\%$ for $t<30$) and without
OAA ($26.33\%$ for $t<30$). The success probability of the modified multi-
product algorithms thus can be amplified by OAA. Points denote experimental
data, and lines refer to their theoretical predictions. Error bars ($\pm
1\sigma$) are estimated from the photon Poissonian statistics.

Assuming the first row of $C^{\prime}$ is
$\\{m_{1}^{\prime},m_{2}^{\prime},m_{3}^{\prime},m_{4}^{\prime}\\}$ (arbitrary
complex numbers), we obtain the output state of data-register as:

$\displaystyle\begin{split}\ket{\Psi}_{\text{data}}=&(m_{1}m_{1}^{\prime}A_{1}+m_{2}m_{2}^{\prime}A_{2}+m_{3}m_{3}^{\prime}A_{3}+m_{4}m_{4}^{\prime}A_{4})\ket{00,\psi}\\\
=&(m_{1}m_{1}^{\prime}A_{1}+m_{2}m_{2}^{\prime}A_{2}+m_{3}m_{3}^{\prime}A_{3}+m_{4}m_{4}^{\prime}A_{4})\ket{\psi},\end{split}$
(13)

where we have removed the layer index for clarity. Though $m_{i}$ and
$m_{i}^{\prime}$ can be chosen arbitrarily, the combined coefficients
$m_{i}m_{i}^{\prime}={c_{i}}/{\sum_{i=1}^{4}|c_{i}|}$ can be optimized to
improve the success probability of the algorithm. When $m_{i}=m_{i}^{\prime}$,
the success probability of LCU becomes the largest (see proof in Supplementary
Information). For this reason, we choose $C^{\prime}$ to be $C^{T}$ (see
Fig.2a), so that the elements in first column of $C$ and first row of $C^{T}$
are the same.

### Experimental benchmarking of multi-product algorithms

We benchmark the modified multi-product algorithms in our LCU quantum
simulator to simulate the dynamics of a Hamiltonian describing the Rabi-type
interactions of an electron spin and a nuclear spin in the rotating frame of
external electromagnetic field frequency. The Hamiltonian $\mathcal{H}$ is
written as:

$\mathcal{H}=\frac{\Omega}{2}\sigma_{x}^{e}+\frac{\delta}{2}\sigma_{z}^{e}+\ket{1}_{e}\bra{1}\otimes(\textbf{E}_{1}\ket{0}_{n}\bra{0}+\textbf{E}_{2}\ket{1}_{n}\bra{1}),$
(14)

where $\sigma_{x}$ and $\sigma_{z}$ are Pauli matrices, subscript and
superscript of $n$ and $e$ represent the nuclear and electron spins,
respectively, $\ket{0}_{n}$ and $\ket{1}_{n}$ represent the ground state and
first excited state with eigenenergies of $E_{1}$ and $E_{2}$, and $\Omega$ is
the frequency of the external electromagnetic field. The Hamiltonian is
defined by the following parameters in experiment,
$E_{1}=0.3,E_{2}=0.7,\Omega=0.2,\delta=0.5$. We use the LCU quantum simulator
to emulate the unitary $U(t)=\text{exp}(-i\mathcal{H}t)$. The operators
{$A_{1},A_{2},A_{3},A_{4}$} are chosen as {$S_{1}^{2}(t/2)$, $S_{1}^{4}(t/4)$,
$S_{1}^{8}(t/8)$, $S_{1}^{16}(t/16)$}, respectively. The $S_{1}(t)$ is second-
order Trotter product of
$e^{-i\mathcal{H}_{1}t/2}e^{-i\mathcal{H}_{2}t}e^{-i\mathcal{H}_{1}t/2}$,
where $\mathcal{H}_{1}$ is the first two terms in Eq.(14), $\mathcal{H}_{2}$
is the last term.

Fig.4a shows experimental probability distributions for the $\ket{11}$ state
measured in the LCU simulator, emulating the dynamic evolution of a $\ket{01}$
initial state governed by the Hamiltonian. We compare the results of modified
multi-product algorithm (combination of $S_{1}^{2}(t/2)$, $S_{1}^{4}(t/4)$,
$S_{1}^{8}(t/8)$ and $S_{1}^{16}(t/16)$) with standard Trotterization (e.g.,
$S_{1}^{16}(t/16)$) and original multi-product algorithm (combination of
$S_{1}(t)$, $S_{1}^{2}(t/2)$, $S_{1}^{3}(t/3)$ and $S_{1}^{16}(t/16)$). It
shows that, for $t\leq 30$, the modified multi-product algorithm can
approximate the exact solution more precisely than the other two algorithms.
Their discrepancies to the exact result are plotted in Fig.4b. For
$t\textgreater 30$, both original and modified multi-product show deviation
from the exact solution due to high-order error and the non-unitary effect.

Figure 5(a-h) reports experimental dynamics for the four logical states
measured in the quantum simulator, when the initial state is chosen as
$\sqrt{0.3}\ket{00}+\sqrt{0.7}\ket{01}$, i.e.,
$\sqrt{0.3}\ket{0}_{e}\ket{0}_{n}+\sqrt{0.7}\ket{0}_{e}\ket{1}_{n}$. Both
modified multi-product algorithm before OAA (Figs.5(a-d)) and after OAA
(Figs.5(e-h)) are implemented. Note that the OAA circuits were complied and
implemented by iteratively input into the quantum simulator. Experimental
results well agree with their theoretical predictions, and a mean of classical
statistical fidelities of $F_{c}=0.996\pm 0.005$ and $F_{c}=0.996\pm 0.004$
are obtained, respectively, for the modified multi-product algorithm with and
without OAA. The $F_{c}$ is defined as $(\sum_{i}\sqrt{p_{i}q_{i}})^{2}$,
where $p_{i}$ and $q_{i}$ are measured distribution and theoretical
distribution respectively. Moreover, we measured the success probability of
algorithms, as shown in Fig 5i. Experimental results show that, when $t\leq
30$, the success probability $P$ is about $26.33\%$ in the modified multi-
product algorithm before OAA step. We then implement OAA and obtain the
amplified probability. As the initial $Pr$ from LCU was approximated to
$26.33\%$, it requires only one step of amplification, i.e. $N=1$. The OAA
circuit in Fig.2b can be simplified to $WRW^{\dagger}RW$, and compiled in the
simulator. By implementing the OAA, we amplify the success probability to
$99.79\%$ at $t\leq 30$, approaching a deterministic probability. All measured
probabilities are consistent with theoretical predictions. When $t>30$, due to
the non-unitary LCU, the high-level success probability however cannot be
retained.

Overall we have proposed and demonstrated a modified multi-product algorithm.
By combing the multi-product and OAA algorithms, it can improve the simulation
precision and relax the success probability constraints. The algorithm is
certificated experimentally in a small-scale silicon-photonic quantum
simulator. Moreover, the linearly combined operations are not necessarily
unitary (mostly, they are non-unitary), implying that LCU can be used to
simulate the dynamics of non-Hermitian systems. The quantum algorithms and
quantum harware could be scaled up to provide an efficient solution to
simulate the dynamics of physical and molecular systems.

### Acknowledgements

We acknowledge support from the Innovation Program for Quantum Science and
Technology (no. 2021ZD0301500), the National Key R$\&$D Program of China (no
2019YFA0308702), the Natural Science Foundation of China (no 61975001),
Beijing Natural Science Foundation (Z190005), and Key R$\&$D Program of
Guangdong Province (2018B030329001).

### Author contributions

Y.Y. and Y.C. equally contributed to this work. Y.Y., Y.C. and J.H.
implemented the experiment. Y.Y., Y.C. and C.Z. provided theoretical analysis.
Q.G. and J.W. managed the project. Y.Y., Y.C., and J.W. wrote the manuscript.

### Competing interests:

The authors declare no competing interests.

### Data availability

The data that support the plots within this paper and other findings of this
study are available from the corresponding author upon reasonable request.

## References

  * [1] I. M. Georgescu, S. Ashhab and Franco Nori  “Quantum simulation”  In _Review of Modern Physics_ 86, 2014, pp. 153–185
  * [2] Sam McArdle et al.  “Quantum computational chemistry”  In _Reviews of Modern Physics_ 92.1 APS, 2020, pp. 015003
  * [3] Hale F Trotter  “On the product of semi-groups of operators”  In _Proceedings of the American Mathematical Society_ 10.4 JSTOR, 1959, pp. 545–551
  * [4] Masuo Suzuki  “Generalized Trotter’s formula and systematic approximants of exponential operators and inner derivations with applications to many-body problems”  In _Communications in Mathematical Physics_ 51.2 Springer, 1976, pp. 183–190
  * [5] Seth Lloyd  “Universal quantum simulators”  In _Science_ 273.5278 American Association for the Advancement of Science, 1996, pp. 1073–1078
  * [6] Alán Aspuru-Guzik, Anthony D Dutoi, Peter J Love and Martin Head-Gordon  “Simulated quantum computation of molecular energies”  In _Science_ 309.5741 American Association for the Advancement of Science, 2005, pp. 1704–1707
  * [7] Dominic W Berry et al.  “Simulating Hamiltonian dynamics with a truncated Taylor series”  In _Physical Review Letters_ 114.9 APS, 2015, pp. 090502
  * [8] Dominic W Berry et al.  “Exponential improvement in precision for simulating sparse Hamiltonians”  In _Forum of Mathematics, Sigma_ 5, 2017  Cambridge University Press
  * [9] Guang Hao Low and Isaac L Chuang  “Hamiltonian simulation by qubitization”  In _Quantum_ 3 Verein zur Förderung des Open Access Publizierens in den Quantenwissenschaften, 2019, pp. 163
  * [10] Guang Hao Low and Isaac L Chuang  “Optimal Hamiltonian simulation by quantum signal processing”  In _Physical Review Letters_ 118.1 APS, 2017, pp. 010501
  * [11] Earl Campbell  “Random compiler for fast Hamiltonian simulation”  In _Physical review letters_ 123.7 APS, 2019, pp. 070503
  * [12] Nathan Wiebe, Dominic W Berry, Peter Høyer and Barry C Sanders  “Simulating quantum dynamics on a quantum computer”  In _Journal of Physics A: Mathematical and Theoretical_ 44.44 IOP Publishing, 2011, pp. 445308
  * [13] Andrew M. Childs and Nathan Wiebe  “Hamiltonian simulation using linear combinations of unitary operations”  In _Quantum Information & Computation_, 2012, pp. 901–924
  * [14] Dominic W. Berry and Andrew M. Childs  “Black-box Hamiltonian simulation and unitary implementation”  In _Quantum Information & Computation_, 2012, pp. 29–62
  * [15] Andrew M Childs  “On the relationship between continuous-and discrete-time quantum walk”  In _Communications in Mathematical Physics_ 294.2 Springer, 2010, pp. 581–603
  * [16] Ryan Babbush et al.  “Chemical basis of Trotter-Suzuki errors in quantum chemistry simulation”  In _Physical Review A_ 91.2 APS, 2015, pp. 022311
  * [17] Markus Heyl, Philipp Hauke and Peter Zoller  “Quantum localization bounds Trotter errors in digital quantum simulation”  In _Science Advances_ 5.4 American Association for the Advancement of Science, 2019, pp. eaau8342
  * [18] AT Sornborger and Ewan D Stewart  “Higher-order methods for simulations on quantum computers”  In _Physical Review A_ 60.3 APS, 1999, pp. 1956
  * [19] Dominic W Berry, Graeme Ahokas, Richard Cleve and Barry C Sanders  “Efficient quantum algorithms for simulating sparse Hamiltonians”  In _Communications in Mathematical Physics_ 270.2 Springer, 2007, pp. 359–371
  * [20] Shi-jie Wei, Zeng-rong Zhou, Dong Ruan and Gui-Lu Long  “Realization of the algorithm for system of linear equations in duality quantum computing”  In _2017 IEEE 85th Vehicular Technology Conference (VTC Spring)_ , 2017, pp. 1–4  IEEE
  * [21] Ryan J Marshman, Austin P Lund, Peter P Rohde and Timothy C Ralph  “Passive quantum error correction of linear optics networks through error averaging”  In _Physical Review A_ 97.2 APS, 2018, pp. 022324
  * [22] Chao Zheng and Shijie Wei  “Duality Quantum Simulation of the Yang-Baxter Equation”  In _International Journal of Theoretical Physics_ 57.7 Springer, 2018, pp. 2203–2212
  * [23] Long Gui-Lu  “General quantum interference principle and duality computer”  In _Communications in Theoretical Physics_ 45.5 IOP Publishing, 2006, pp. 825
  * [24] He-Liang Huang, Dachao Wu, Daojin Fan and Xiaobo Zhu  “Superconducting quantum computing: a review”  In _Science China Information Sciences_ 63.8, 2020, pp. 180501
  * [25] C. Monroe et al.  “Programmable quantum simulations of spin systems with trapped ions”  In _Reviews of Modern Physics_ 93, 2021, pp. 025001
  * [26] Sergei Slussarenko and Geoff J. Pryde  “Photonic quantum information processing: A concise review”  In _Appl. Phys. Rev._ 6.4, 2019, pp. 041303
  * [27] Xiao-Qi Zhou et al.  “Adding control to arbitrary unknown quantum operations”  In _Nature Communications_ , 2011, pp. 413
  * [28] Jianwei Wang et al.  “Experimental quantum Hamiltonian learning”  In _Nature Physics_ 13, 2017, pp. 551–555
  * [29] Raffaele Santagati et al.  “Witnessing eigenstates for quantum simulation of Hamiltonian spectra”  In _Science Advances_ 4.1, 2018, pp. aap9646
  * [30] Yulin Chi et al.  “A programmable qudit-based quantum processor”  In _Nature Communications_ 13.1 Nature Publishing Group, 2022, pp. 1–10
  * [31] Raj B. Patel et al.  “A quantum Fredkin gate”  In _Science Advances_ 2.3, 2016, pp. e1501531
  * [32] Jianwei Wang, Fabio Sciarrino, Anthony Laing and Mark G. Thompson  “Integrated photonic quantum technologies”  In _Nature Photonics_ 14, 2020, pp. 273–284
  * [33] Caterina Vigliar et al.  “Error-protected qubits in a silicon photonic chip”  In _Nature Physics_ 17.10, 2021, pp. 1137–1143
  * [34] Jianwei Wang et al.  “Multidimensional quantum entanglement with large-scale integrated optics”  In _Science_ 360.6386, 2018, pp. 285–291
  * [35] Xiaogang Qiang et al.  “Large-scale silicon quantum photonics implementing arbitrary two-qubit processing”  In _Nature Photonics_ 12.9, 2018, pp. 534–539
  * [36] Wolfram HP Pernice et al.  “High-speed and high-efficiency travelling wave single-photon detectors embedded in nanophotonic circuits”  In _Nature communications_ 3.1 Nature Publishing Group, 2012, pp. 1–10
  * [37] Siu A Chin  “Multi-product splitting and Runge-Kutta-Nyström integrators”  In _Celestial Mechanics and Dynamical Astronomy_ 106.4 Springer, 2010, pp. 391–406

## Supplementary Information:
Simulating Hamiltonian dynamics in a programmable photonic quantum processor
using linear combinations of unitary operations

Yue Yu1,⋆, Yulin Chi1,⋆, Chonghao Zhai1, Jieshan Huang1, Qihuang
Gong1,2,3,4,5, Jianwei Wang1,2,3,4,5,†

1 State Key Laboratory for Mesoscopic Physics, School of Physics, Peking
University, Beijing, 100871, China
2 Frontiers Science Center for Nano-optoelectronics & Collaborative Innovation
Center of Quantum Matter, Peking University, Beijing, 100871, China
3 Collaborative Innovation Center of Extreme Optics, Shanxi University,
Taiyuan 030006, Shanxi, China
4 Peking University Yangtze Delta Institute of Optoelectronics, Nantong
226010, Jiangsu, China.
5 Hefei National Laboratory, Hefei 230088, China

Device fabrication. The integrated photonic four-qubit quantum simulator used
to implement the linear combinations of unitaries for Hamiltonian simulation
is designed and fabricated on the silicon nanophotonics platform. The devices
are fabricated by the standard CMOS (complementary metal oxide semiconductor)
process. First, spin a layer of photoresist on an 8-inch SOI (silicon on
insulator) wafer with 220 nm thick top silicon and 3 µm thick buried oxide.
248 nm deep ultraviolet (DUV) lithography is used to define the pattern of the
silicon layer on the photoresist where single-mode waveguides are designed
with a width of 500nm (widened to 4 microns in some areas to reduce
transmission losses). The pattern is transferred from the photoresist layer to
the silicon layer by double inductively coupled plasma (ICP) etching process
to form waveguide and grating couplers. A deeply etched waveguide with an
etching depth of 220 nm is used for the SFWM photon source, beam
splitter(multimode interferometer) and phase shifter. A shallow etched
waveguide with an etching depth of 70 nm is used for waveguide crossovers and
grating couplers. A 1 µm thick SiO2 layer is deposited on the SOI wafer by
plasma-enhanced chemical vapor deposition (PECVD) as an isolation layer
between the waveguide and the metal heater. Then, a 10 nm thick Ti adhesive
layer, a 20 nm thick TiN barrier layer, an 800 nm thick AlCu layer and a 20 nm
thick TiN antireflection layer were deposited by physical vapor deposition
(PVD), in which AlCu was used as a conductive layer and patterned by DUV
lithography and etching process to form electrodes. Then, a 50 nm thick TiN
layer for the thermooptical phase shifter was deposited by PECVD and patterned
by DUV lithography and etching process. Finally, 1 µm thick SiO2 is deposited
as the top coating. The bonding pad opening process is then carried out to
remove the SiO2 and TiN after DUV lithography in specific areas designed for
wire bonding.

Experimental setup. A tunable continuous-wave laser central at a wavelength of
1550.12 nm was amplified to 100 mW by an erbium doped fiber amplifier (EDFA).
Then the amplified laser is filtered by array waveguide gratings (AWG)
wavelength-division multiplexing (WDM) to remove noise from the amplifier, and
then coupled to the chip through on-chip grating couplers. In order to improve
the coupling efficiency of the grating coupler, we use a fiber polatization
controller to adjust the polarization of the laser before the chip to achieve
the highest coupling efficiency, which is about -4 dB each port. The entangled
photon pairs are generated in on-chip sources through the spontaneous four-
wave mixing (SFWM) effect of silicon from the pump laser. We chose 1545.32nm
and 1554.94nm as the wavelength of idler and signal photons, and photons of
other wavelengths and the residual pump light are filtered out by off-chip AWG
with a bandwidth of 0.9 nm and extinction ratio $\textgreater 90$ dB. The
entangled photons were detected by superconducting nanowire single-photon
detectors (SNSPD) with 85% efficiency in average and coincident counting
measurements were conducted using a multichannel time interval analyzer (TIA).
The resulting two-photon coincidence count rate is at the order of kHz. The
integrated photonic chip is wire bonded on a printed circuit board (PCB) and
the PCB is fixed with thermal epoxy on a copper constant temperature terrace
to maintain the modulation temperature of the thermo-optic phase modulator,
providing stable temperature conditions and suppressing thermal crosstalks. At
the design of practical devices, we use curved waveguides to compensate the
length of different structures to ensure coherence. At the same time, we also
designed several 1% couplers at some positions not marked in the figure to
calibrate the phase modulators on the chip. They all use the same on-chip
grating couplers to couple with the off-chip fibers.

Linear combination of unitary operations. For readers unfamiliar with LCU, we
provide a brief introduction to it here. The LCU algorithm utilizes the
entanglement between two quantum systems: N-dimensional ancillary register
$\ket{\cdot}_{a}$ and M-dimensional data register $\ket{\cdot}_{d}$, and non-
deterministically generates the linear combination of $N$ unitary gates
$\sum_{i=1}^{N}c_{i}A_{i}$ ($c_{i}$ is coefficient and $A_{i}$ is unitary
gate) that acts on data register.

Firstly, a product state, $\ket{0}_{a}\ket{\psi}_{d}$, is generated as the
input state of LCU circuit. Since there is no entanglement between ancillary
and data register in this quantum state, it is relatively easy to generate.

Secondly, we implement a N-qubit gate $C$ on the ancillary register:

$\displaystyle
C=\begin{bmatrix}\sqrt{\frac{c_{1}}{\sum_{i=1}^{N}|c_{i}|}}&*&\cdots&*\\\
\sqrt{\frac{c_{2}}{\sum_{i=1}^{N}|c_{i}|}}&*&\cdots&*\\\
\vdots&\vdots&\ddots&\vdots\\\
\sqrt{\frac{c_{N}}{\sum_{i=1}^{N}|c_{i}|}}&*&\cdots&*\\\ \end{bmatrix}$ (15)

It can be seen from the above expression that the j-th element in first column
of $C$’s matrix representation is $\sqrt{c_{j}/\sum_{i=1}^{N}|c_{i}|}$. We
don’t care about elements in other columns since only elements in the first
column affect the evolution of $\ket{0}_{a}$. After this step, the quantum
state becomes

$\displaystyle\sqrt{\frac{1}{\sum_{i=1}^{N}|c_{i}|}}\sum_{j=1}^{N}\sqrt{c_{j}}\ket{j-1}_{a}\ket{\psi}_{d}$
(16)

Thirdly, we implement N C(N)U(M) gates (M-qubit gate controlled by N control
qubits) $A_{i}$, $i=1,2,\cdots,N$. These gates are controlled by ancillary
register and act on data register. This step projects the quantum state into
an output of

$\displaystyle\sqrt{\frac{1}{\sum_{i=1}^{N}|c_{i}|}}\sum_{j=1}^{N}\sqrt{c_{j}}\ket{j-1}_{a}A_{j}\ket{\psi}_{d}$
(17)

Finally, we implement N-qubit gate $C^{T}$ on ancillary register. The matrix
representation of $C^{T}$ is

$\displaystyle
C^{T}=\begin{bmatrix}\sqrt{\frac{c_{1}}{\sum_{i=1}^{N}|c_{i}|}}&\sqrt{\frac{c_{2}}{\sum_{i=1}^{N}|c_{i}|}}&\cdots&\sqrt{\frac{c_{N}}{\sum_{i=1}^{N}|c_{i}|}}\\\
*&*&\cdots&*\\\ \vdots&\vdots&\ddots&\vdots\\\ *&*&\cdots&*\\\ \end{bmatrix}$
(18)

This will lead to following output:

$\displaystyle\frac{1}{\sum_{i=1}^{N}|c_{i}|}\ket{0}_{a}\sum_{j=1}^{N}c_{j}A_{j}\ket{\psi}_{d}+\ket{1}_{a}\cdots+\ket{2}_{a}\cdots+\cdots$
(19)

It can be seen from the above expression that each ancillary register state
$\ket{j}_{a}$ corresponds to a linear combination of $A_{i}$, but only the
combination after $\ket{0}_{a}$ is what we want. Therefore, we post-select the
ancillary register with projector $\ket{0}_{a}\bra{0}$. If we assume
$\left\|\sum_{j=1}^{N}c_{j}A_{j}\ket{\psi}_{d}\right\|=1$ (this assumption
does not always hold, for example, when $\sum_{j=1}^{N}c_{j}A_{j}$ is not
unitary), then the post-selection probability is
$\left(1/\sum_{i=1}^{N}|c_{i}|\right)^{2}$. Generally, this possibility drops
quickly as $N$ increases.

Oblivious amplitude amplification. Oblivious Amplitude Amplification [8] (OAA)
is an algorithm proposed to solve the low success probability problem of LCU.
It is very similar to Grover algorithm and the post-selection probability can
be amplified by multiple iterations of the LCU circuit. To describe its main
structure, we first define the following operators:

$\displaystyle\begin{split}W\ket{\Psi}&=\sin(\theta)\ket{\Phi}+\cos(\theta)\ket{\Phi^{\perp}}\\\
P&=\ket{0}\bra{0}\otimes I\\\ R&=(1-2\ket{0}\bra{0})\otimes I\end{split}$ (20)

where $\ket{\Psi},\ket{\Phi}$ and $\ket{\Phi^{\perp}}$ have following
relationships:

$\displaystyle\ket{\Psi}$ $\displaystyle=\ket{0}\ket{\psi}$ (21)
$\displaystyle\ket{\Phi}$ $\displaystyle=\ket{0}U\ket{\psi}$ (22)
$\displaystyle P$ $\displaystyle\ket{\Phi^{\perp}}=0$ (23)

$\ket{\psi}$ is arbitrary quantum state and $U$ is unitary operator.
Obviously, $W$ can be used to describe a general LCU circuit and $P$ is the
corresponding post-selection projector. Based on the above definitions, OAA
tells us that the following equation holds:

$\displaystyle(-WRW^{\dagger}R)^{N}W\mathinner{|\Psi\rangle}=\sin[(2N+1)\theta]\mathinner{|\Phi\rangle}+\cos[(2N+1)\theta]\mathinner{|\Phi^{\perp}\rangle}$
(24)

Therefore, we can amplify the post-selection probability from
$\sin^{2}(\theta)$ to $\sin^{2}((2N+1)\theta)$ with OAA.

The verification process is shown below:

Firstly, we define state $\ket{\Psi^{\perp}}$ as

$\displaystyle
W\ket{\Psi^{\perp}}=\cos(\theta)\ket{\Phi}-\sin(\theta)\ket{\Phi^{\perp}}$
(25)

It can be easily proved that the state $\ket{\Psi^{\perp}}$ always exists.

The following lemma will be very useful in the verification of OAA:

######  Lemma 1.

$P\ket{\Psi^{\perp}}=0$ when $\theta\neq 0$

###### Proof.

We define operator $Q:=(\bra{0}\otimes I)W^{\dagger}PW(\ket{0}\otimes I)$.
Then $\forall\ket{\psi}$, we have:

$\displaystyle\begin{split}\mathinner{\langle\psi|Q|\psi\rangle}&=\left\|PW(\mathinner{|0\rangle}\otimes
I)\mathinner{|\psi\rangle}\right\|\\\
&=\left\|PW\mathinner{|\Psi\rangle}\right\|\\\
&=\left\|P\left(\sin(\theta)\mathinner{|\Phi\rangle}+\cos(\theta)\mathinner{|\Phi^{\perp}\rangle}\right)\right\|\\\
&=\sin^{2}(\theta)\end{split}$ (26)

Since this holds for all $\ket{\psi}$, we have $Q=\sin^{2}(\theta)I$,
$Q\ket{\psi}=\sin^{2}(\theta)\ket{\psi}$.

From another direction, we can calculate $Q\ket{\psi}$ directly:

$\displaystyle\begin{split}Q\mathinner{|\psi\rangle}&=(\mathinner{\langle
0|}\otimes I)W^{\dagger}PW(\mathinner{|0\rangle}\otimes
I)\mathinner{|\psi\rangle}\\\ &=(\mathinner{\langle 0|}\otimes
I)W^{\dagger}PW\mathinner{|\Psi\rangle}\\\ &=\sin(\theta)(\mathinner{\langle
0|}\otimes I)W^{\dagger}\mathinner{|\Phi\rangle}\\\ \end{split}$ (27)

Therefore

$\displaystyle\sin^{2}(\theta)\ket{\psi}=\sin(\theta)(\mathinner{\langle
0|}\otimes I)W^{\dagger}\mathinner{|\Phi\rangle}$ (29)

From formula 20 and 25, we have:

$\displaystyle
W^{\dagger}\ket{\Phi}=\sin(\theta)\ket{\Psi}+\cos(\theta)\ket{\Psi^{\perp}}$
(30)

Bring it back to formula 29

$\displaystyle\begin{split}\sin^{2}(\theta)\mathinner{|\psi\rangle}&=\sin(\theta)(\mathinner{\langle
0|}\otimes I)W^{\dagger}\mathinner{|\Phi\rangle}\\\
&=\sin(\theta)(\mathinner{\langle 0|}\otimes
I)(\sin(\theta)\mathinner{|\Psi\rangle}+\cos(\theta)\mathinner{|\Psi^{\perp}\rangle})\\\
&=\sin(\theta)\mathinner{|\psi\rangle}+\sin(\theta)\cos(\theta)(\mathinner{\langle
0|}\otimes I)\mathinner{|\Psi^{\perp}\rangle}\end{split}$ (31)

Therefore

$\displaystyle(\bra{0}\otimes I)\ket{\Psi^{\perp}}=P\ket{\Psi^{\perp}}=0$ (33)

∎

Based on Lemma 1, we can prove the amplification effect of OAA:

######  Theorem 1.

$(-WRW^{\dagger}R)^{N}W\ket{\Psi}=\sin[(2N+1)\theta]\ket{\Phi}+\cos[(2t+1)\theta]\ket{\Phi^{\perp}}$

###### Proof.

We define $S:=-WRW^{\dagger}R$. Based on the previous discussion, we have:

$\displaystyle W\mathinner{|\Psi\rangle}$
$\displaystyle=\sin(\theta)\mathinner{|\Phi\rangle}+\cos(\theta)\mathinner{|\Phi^{\perp}\rangle}$
(34) $\displaystyle W\mathinner{|\Psi^{\perp}\rangle}$
$\displaystyle=\cos(\theta)\mathinner{|\Phi\rangle}-\sin(\theta)\mathinner{|\Phi^{\perp}\rangle}$
(35) $\displaystyle W^{\dagger}\mathinner{|\Phi\rangle}$
$\displaystyle=\sin(\theta)\mathinner{|\Psi\rangle}+\cos(\theta)\mathinner{|\Psi^{\perp}\rangle}$
(36) $\displaystyle W^{\dagger}\mathinner{|\Phi^{\perp}\rangle}$
$\displaystyle=\cos(\theta)\mathinner{|\Psi\rangle}-\sin(\theta)\mathinner{|\Psi^{\perp}\rangle}$
(37)

Therefore

$\displaystyle
SW\mathinner{|\Psi\rangle}=\sin(\theta)S\mathinner{|\Phi\rangle}+\cos(\theta)S\mathinner{|\Phi^{\perp}\rangle}$
(38)

According to Lemma 1, we can write down following relationships:

$\displaystyle R\ket{\Phi}$ $\displaystyle=\ket{\Phi}$ (39) $\displaystyle
R\ket{\Phi^{\perp}}$ $\displaystyle=-\ket{\Phi^{\perp}}$ (40) $\displaystyle
R\ket{\Psi}$ $\displaystyle=\ket{\Psi}$ (41) $\displaystyle
R\ket{\Psi^{\perp}}$ $\displaystyle=-\ket{\Psi^{\perp}}$ (42)

Therefore

$\displaystyle\begin{split}S\mathinner{|\Phi\rangle}&=-WRW^{\dagger}R\mathinner{|\Phi\rangle}=-WRW^{\dagger}\mathinner{|\Phi\rangle}\\\
&=-WR\left(\sin(\theta)\mathinner{|\Psi\rangle}+\cos(\theta)\mathinner{|\Psi^{\perp}\rangle}\right)\\\
&=W\left(-\sin(\theta)\mathinner{|\Psi\rangle}+\cos(\theta)\mathinner{|\Psi^{\perp}\rangle}\right)\\\
&=(\cos^{2}(\theta)-\sin^{2}(\theta))\mathinner{|\Phi\rangle}-2\sin(\theta)\cos(\theta)\mathinner{|\Phi^{\perp}\rangle}\\\
&=\cos(2\theta)\mathinner{|\Phi\rangle}-\sin(2\theta)\mathinner{|\Phi^{\perp}\rangle}\end{split}$
(43)

$\displaystyle\begin{split}S\mathinner{|\Phi^{\perp}\rangle}&=-WRW^{\dagger}R\mathinner{|\Phi^{\perp}\rangle}=WRW^{\dagger}\mathinner{|\Phi^{\perp}\rangle}\\\
&=WR\left(\cos(\theta)\mathinner{|\Psi\rangle}-\sin(\theta)\mathinner{|\Psi^{\perp}\rangle}\right)\\\
&=W\left(\cos(\theta)\mathinner{|\Psi\rangle}+\sin(\theta)\mathinner{|\Psi^{\perp}\rangle}\right)\\\
&=2\sin(\theta)\cos(\theta)\mathinner{|\Phi\rangle}+(\cos^{2}(\theta)-\sin^{2}(\theta))\mathinner{|\Phi^{\perp}\rangle}\\\
&=\sin(2\theta)\mathinner{|\Phi\rangle}+\cos(2\theta)\mathinner{|\Psi\Phi^{\perp}\rangle}\end{split}$
(44)

Take these back to formula 38, we have

$\displaystyle
SW\mathinner{|\Psi\rangle}=\sin(3\theta)\mathinner{|\Phi\rangle}+\cos(3\theta)\mathinner{|\Phi^{\perp}\rangle}$
(45)

Similarly, we can further prove that

$\displaystyle
S^{N}W\mathinner{|\Psi\rangle}=\sin[(2N+1)\theta]\mathinner{|\Phi\rangle}+\cos[(2N+1)\theta]\mathinner{|\Phi^{\perp}\rangle}$
(46)

∎

Error analysis of OAA. OAA is originally used to amplify the LCU with unitary
target operator. When the target operator implemented by LCU is unitary and
the success probability of LCU is exactly $25\%$, OAA can amplify the success
probability into $100\%$ without any additional error. However, this condition
does not always hold.

We define $P:=\ket{0}\bra{0}\otimes I$, $R:=I-2P$ and denote the circuit of
LCU as $W$, then we have

$\displaystyle PW\ket{0}\ket{\psi}=s\ket{0}U\ket{\psi}$ (47)

Where $U$ is the target operator implemented by LCU, $s$ is the complex
amplitude of target operator and success probability is $|s|^{2}$. We then
denote the circuit of OAA as $A=WRW^{\dagger}RW$, therefore

$\displaystyle PA\ket{0}\ket{\psi}=(3PW-4WPW^{\dagger}PW)\ket{0}\ket{\psi}$
(48)

Following the conclusion proposed by Berry et al.[7], we obtain:

$\displaystyle PA\ket{0}\ket{\psi}=(3sU-4s^{3}UU^{\dagger}U)\ket{\psi}$ (49)

When $\left\|UU^{\dagger}-I\right\|=\mathcal{O}(\delta)$ and $s=0.5+\Delta$,
we can bound the error of OAA:

$\displaystyle\left\|\frac{PA\ket{\psi}}{\left\|PA\ket{\psi}\right\|}-\frac{PW\ket{\psi}}{\left\|PW\ket{\psi}\right\|}\right\|=\left\|\frac{PA\ket{\psi}}{\left\|PA\ket{\psi}\right\|}-U\ket{\psi}\right\|\approx(\frac{1}{2}+3\Delta)\mathcal{O}(\delta)$
(50)

So when the success probability of LCU is close to $25\%$ (for example,
probability deviation $\leq 5\%$), it will not affect the error of OAA too
much. If we follow the choice $L(q)=a\cdot 2^{q}$, then $\Delta\approx 8\times
10^{-3}$ and error $\approx 0.52\mathcal{O}(\delta)$. We need to emphasize
here that $\mathcal{O}(\delta)$ represents the non-unitary effect of LCU, and
the error of LCU is not necessarily equal to $\mathcal{O}(\delta)$. However,
we will prove in the next section that the error of LCU is larger than
$\mathcal{O}(\delta)$ in unitary simulation task, which can help us bound the
overall error of modified algorithm.

Error analysis of modified algorithm. There are two source of error in our
modified algorithm: error introduced by OAA amplification and intrinsic error
of non-unitary LCU.

Firstly, we focus on the amplification error of OAA. As we have discussed
previously, under proper choice of linear combination coefficients in LCU, the
amplification error is

$\displaystyle\left\|E_{oaa}\right\|\approx\frac{\mathcal{O}(\delta)}{2}$ (51)

where $\mathcal{O}(\delta)=\left\|UU^{\dagger}-I\right\|$, $U$ is the target
operator of LCU. Notice that the goal of modified algorithm is to simulate a
unitary operator $U_{exact}$, therefore we denote $U=U_{exact}+E_{lcu}$,
($E_{lcu}$ is not necessarily unitary), then we have

$\displaystyle\begin{split}\left\|UU^{\dagger}-I\right\|&=\left\|UU_{exact}^{\dagger}+E_{lcu}U^{\dagger}+UE_{lcu}^{\dagger}+E_{lcu}E_{lcu}^{\dagger}-I\right\|\\\
&=\left\|E_{lcu}U^{\dagger}+UE_{lcu}^{\dagger}+E_{lcu}E_{lcu}^{\dagger}\right\|\\\
&\leq\left\|E_{lcu}U^{\dagger}\right\|+\left\|UE_{lcu}^{\dagger}\right\|+\left\|E_{lcu}E_{lcu}^{\dagger}\right\|\\\
&\leq 2\left\|E_{lcu}\right\|+\left\|E_{lcu}\right\|^{2}\\\ &\approx
2\left\|E_{lcu}\right\|\end{split}$ (52)

Therefore

$\displaystyle\left\|E_{lcu}\right\|\geq\frac{\mathcal{O}(\delta)}{2}\approx\left\|E_{oaa}\right\|$
(53)

So the overall error of the modified algorithm
$\left\|E_{total}\right\|\leq\left\|E_{lcu}\right\|+\left\|E_{oaa}\right\|\leq
2\left\|E_{lcu}\right\|$, therefore the error of the modified algorithm is
bounded by error of LCU when combination coefficients are chosen properly.

Next we discuss the error of LCU. The error of multi-product is[37]

$\displaystyle
e^{-i\sum_{j=1}^{m}\mathcal{H}_{j}t}=\sum_{q=1}^{k}c_{q}\mathcal{S}_{1}^{L(q)}(t/L(q))+(-1)^{k-1}E_{2k+1}t^{2k+1}\prod_{q=1}^{k}\frac{1}{L^{2}(q)}+\mathcal{O}(t^{2k+3})$
(54)

If we choose $L(q)=a\cdot 2^{q}$, then the error is

$\displaystyle\left\|E_{lcu}\right\|=\left\|E_{2k+1}\right\|\frac{t^{2k+1}}{a^{2k}2^{(1+k)k}}$
(55)

And then then total error of modified algorithm is bounded as below:

$\displaystyle\left\|E_{total}\right\|\leq\left\|E_{2k+1}\right\|\frac{t^{2k+1}}{a^{2k}2^{k^{2}+k-1}}$
(56)

Comparison between multi-product algorithm and modified version. In this
section, we will discuss the advantages and drawbacks of multi-product
algorithm and its modified version. The advantage of modified version is its
high success probability and precision. Here we will compare the two version
in details. In original version [13] , $L(q)$ is chosen to be

$\displaystyle L(q)=\left\\{\begin{array}[]{ll}q&1\leq q<k\\\ e^{\gamma
k}&q=k\end{array}\right.$ (59)

and the error of multi-product algorithm is

$\displaystyle\left\|E_{2k+1}\right\|t^{2k+1}\frac{e^{-2\gamma
k}}{[(k-1)!]^{2}}$ (60)

For modified version, we choose $L(q)$ the nearest integer to $e^{\gamma
k}\cdot 2^{q-k}/3$, so the modified version has the same circuit depth with
original version (Trotter products in LCU are commutative). In this case, the
error of modified version is

$\displaystyle\left\|E_{2k+1}\right\|t^{2k+1}9^{k}2^{k^{2}-k+1}e^{-2\gamma
k^{2}}$ (61)

It’s easy to prove that the second error is smaller when $k$ is large.

In contrast, although the original version multi-product algorithm’s precision
is lower, its error grows much slower then modified version. We attribute this
to Trotter formula’s property. The error we calculate only works when the
Taylor expansion’s truncation error is negligible. When the truncation error
can’t be ignored, the error of modified version will grows dramatically, while
the Trotter formula’s error will grow much slower. This is because in original
multi-product algorithm, the Trotter product with the largest iteration number
contributes most of the simulation result (because
$\sum_{q=1}^{k-1}|c_{q}|\ll|c_{k}|$), so it has similar property as Trotter
formula.

Selection of $\bf m_{i}$ and $\bf m_{i}^{\prime}$. When the non-unitary effect
of LCU is insignificant, $m_{i}$ and $m_{i}^{\prime}$ determine the outcome
and success probability of LCU (in the following text, the success probability
refers to the probability at this stage). Assuming that the expected operator
of LCU is $\sum_{i=1}^{k}c_{i}A_{i}$, then $m_{i}$ and $m_{i}^{\prime}$ should
satisfy

$\displaystyle\frac{m_{i}m_{i}^{\prime}}{m_{j}m_{j}^{\prime}}=\frac{c_{i}}{c_{j}}\quad
i,j=1,2,\cdots,k$ (62)

Meanwhile, $\\{m_{1},m_{2},\cdots,m_{k}\\}$ and
$\\{m_{1}^{\prime},m_{2}^{\prime},\cdots,m_{k}^{\prime}\\}$ is the first
column of $C$ and the first row of $C^{\prime}$, respectively. Since $C$ and
$C^{\prime}$ are unitary operator, we have

$\displaystyle\sum_{i=1}^{k}|m_{i}|^{2}=\sum_{i=1}^{k}|m_{i}^{\prime}|^{2}=1$
(63)

The success probability of LCU is

$\displaystyle
P=|\frac{m_{i}m_{i}^{\prime}}{c_{i}}|^{2}=\frac{|m_{i}|^{2}|m_{i}^{\prime}|^{2}}{|c_{i}|^{2}}\quad\forall
i\in\\{1,2,\cdots,k\\}$ (64)

therefore

$\displaystyle\frac{|c_{i}|^{2}}{|m_{i}|^{2}}=\frac{|m_{i}^{\prime}|^{2}}{P}$
(65)
$\displaystyle\sum_{i=1}^{k}\frac{|c_{i}|^{2}}{|m_{i}|^{2}}=\sum_{i=1}^{k}\frac{|m_{i}^{\prime}|^{2}}{P}=\frac{1}{P}$
(66)

The last equality is because of formula 63. Since
$\sum_{j=1}^{k}|m_{j}|^{2}=1$, we have

$\displaystyle\sum_{j=1}^{k}|m_{j}|^{2}\sum_{i=1}^{k}\frac{|c_{i}|^{2}}{|m_{i}|^{2}}=\frac{1}{P}$
(67)

Therefore

$\displaystyle\begin{split}\frac{1}{P}&=\sum_{i=1}^{k}|c_{i}|^{2}+\sum_{i,j=1,i\neq
j}^{k}|c_{i}|^{2}\frac{|m_{j}|^{2}}{|m_{i}|^{2}}\\\
&\geq\sum_{i=1}^{k}|c_{i}|^{2}+\sum_{i,j=1,i\neq j}^{k}|c_{i}||c_{j}|\\\
&=(\sum_{i=1}^{k}|c_{i}|)^{2}\end{split}$ (68)

The inequality is because of
$|c_{i}|^{2}\frac{|m_{j}|^{2}}{|m_{i}|^{2}}+|c_{j}|^{2}\frac{|m_{i}|^{2}}{|m_{j}|^{2}}\geq
2|c_{i}||c_{j}|$. Thus

$\displaystyle P\leq\frac{1}{(\sum_{i=1}^{k}|c_{i}|)^{2}}$ (69)

We can achieve this limit with
$m_{i}=m_{i}^{\prime}=\sqrt{c_{i}/\sum_{i=1}^{k}|c_{i}|}$, therefore the
success probability under this choice is the largest.