summaries: This paper proposes a new class of surrogates called PiRank for ranking metrics optimization. In particular, it uses temperature-controlled relaxation to the permutation matrix to derive a continuous and differentiable sorting operator. Due to the large size of the ranking lists in practical applications, this paper also proposes a divide-and-conquer method to reduce the complexity of metric computation. Experiment results show that the proposed methods can achieve promising results on two popular benchmarks.

summaries: This paper proposes PiRank, a new neural learning-to-rank (LTR) approach based on differentiable sorting operators. The authors present empirical results against two widely used LTR data sets (MSLR-WEB30K and Yahoo! C14).

summaries: This paper tackles the problem of Learning To Rank. The idea is to relax ranking metrics (eg DCG), that are non differentiable with respect to the model parameters theta. Originally, these metrics measure how well the predicted ranking (induced by the scores predicted by the model) places high items with high true relevance labels. The relaxed metrics replace the permutation matrix in the original metrics by a relaxed, unimodal matrix, parametrized by a temperature.  This relaxation was proposed in Neuralsort, but is of quadratic complexity in the total number of items L at each time. In this paper, the authors propose a computationally efficient version of Neuralsort, truncated at the k first items, relying on a divide and conquer strategy. This approach is of much lower complexity, expressed in terms of L,k, and d the depth of the tree.  Finally, the method is evaluated on benchmark learning to rank datasets. It obtains similar or better performance than sota methods.

summaries: The authors provide a new scalable listwise loss for ranking called PiRank.  The loss is defined as 1 - a differentiable relaxation of NDCG metric with temperature-controlled inspired by NeuralSort algorithm. In this setting, the difference with the NDCG is negligeable the temperature tends to 0.  Scalability is ensured by a divide-and-conquer strategy where the sorting relaxation is applied to sub-lists of smaller size and then propagate only on the top items from each sub-list to merge the sort.

abstractText: A key challenge with machine learning approaches for ranking is the gap between the performance metrics of interest and the surrogate loss functions that can be optimized with gradient-based methods. This gap arises because ranking metrics typically involve a sorting operation which is not differentiable w.r.t. the model parameters. Prior works have proposed surrogates that are loosely related to ranking metrics or simple smoothed versions thereof, and often fail to scale to real-world applications. We propose PiRank, a new class of differentiable surrogates for ranking, which employ a continuous, temperature-controlled relaxation to the sorting operator based on NeuralSort [1]. We show that PiRank exactly recovers the desired metrics in the limit of zero temperature and further propose a divideand-conquer extension that scales favorably to large list sizes, both in theory and practice. Empirically, we demonstrate the role of larger list sizes during training and show that PiRank significantly improves over comparable approaches on publicly available internet-scale learning-to-rank benchmarks.

authors:
Aditya Grover
Eric Wang
Aaron Zweig
Stefano Ermon

title: Stochastic optimization of sorting networks via continuous relaxations

venue: In ICLR,

title: Learning to rank for information retrieval

venue: Foundations and Trends R in Information Retrieval,

authors:
David Cossock
Tong Zhang

title: Subset ranking using regression

venue: In COLT,

authors:
Ping Li
Qiang Wu
Christopher J Burges

title: Mcrank: Learning to rank using multiple classification and gradient boosting

venue: In NeurIPS,

authors:
Koby Crammer
Yoram Singer

title: Pranking with ranking

authors:
Amnon Shashua
Anat Levin

title: Ranking with large margin principle: Two approaches

title: Large margin rank boundaries for ordinal regression

venue: Advances in large margin classifiers,

authors:
Yoav Freund
Raj Iyer
Robert E Schapire
Yoram Singer

title: An efficient boosting algorithm for combining preferences

authors:
Chris Burges
Tal Shaked
Erin Renshaw
Ari Lazier
Matt Deeds
Nicole Hamilton
Greg Hullender

title: Learning to rank using gradient descent

venue: In ICML,

title: From ranknet to lambdarank to lambdamart: An overview

authors:
Zhaohui Zheng
Hongyuan Zha
Tong Zhang
Olivier Chapelle
Keke Chen
Gordon Sun

title: A general boosting method and its application to learning ranking functions for web search

venue: NeurIPS,

authors:
Yunbo Cao
Jun Xu
Tie-Yan Liu
Hang Li
Yalou Huang
Hsiao-Wuen Hon

title: Adapting ranking svm to document retrieval

venue: In SIGIR,

authors:
Christopher J.C. Burges
Robert Ragno
Quoc Viet Le

title: Learning to rank with nonsmooth cost functions

authors:
Mingrui Wu
Yi Chang
Zhaohui Zheng
Hongyuan Zha

title: Smoothing DCG for learning to rank: A novel approach using smoothed hinge functions

venue: In CIKM,

authors:
Zhe Cao
Tao Qin
Tie-Yan Liu
Ming-Feng Tsai
Hang Li

title: Learning to rank: from pairwise approach to listwise approach

authors:
Fen Xia
Tie-Yan Liu
Jue Wang
Wensheng Zhang
Hang Li

title: Listwise approach to learning to rank: theory and algorithm

authors:
Jun Xu
Hang Li

title: Adarank: a boosting algorithm for information retrieval

authors:
Yisong Yue
Thomas Finley
Filip Radlinski
Thorsten Joachims

title: A support vector method for optimizing average precision

authors:
Michael Taylor
John Guiver
Stephen Robertson
Tom Minka

title: Softrank: optimizing non-smooth rank metrics

venue: In WSDM,

authors:
Tao Qin
Tie-Yan Liu

title: Introducing LETOR 4.0 Datasets

authors:
Rama Kumar Pasumarthi
Sebastian Bruch
Xuanhui Wang
Cheng Li
Michael Bendersky

title: Tf-ranking: Scalable tensorflow library for learning-to-rank

venue: Springer Science & Business Media,

title: Recall, precision and average precision

venue: Department of Statistics and Actuarial Science, University of Waterloo, Waterloo,

authors:
Kalervo Järvelin
Jaana Kekäläinen

title: Cumulated gain-based evaluation of ir techniques

venue: ACM Transactions on Information Systems,

authors:
Tao Qin
Tie-Yan Liu
Hang Li

title: A general approximation framework for direct optimization of information retrieval measures

venue: Information retrieval,

authors:
Mathieu Blondel
Olivier Teboul
Quentin Berthet
Josip Djolonga

title: Fast differentiable sorting and ranking

authors:
Olivier Chapelle
Mingrui Wu

title: Gradient descent optimization of smoothed information retrieval metrics

authors:
Ryan Prescott Adams
Richard S Zemel

title: Ranking via sinkhorn propagation

venue: arXiv preprint arXiv:1106.1925,

authors:
Gonzalo Mena
David Belanger
Scott Linderman
Jasper Snoek

title: Learning Latent Permutations with Gumbel-Sinkhorn Networks

authors:
Marco Cuturi
Olivier Teboul
Jean-Philippe Vert

title: Differentiable Ranks and Sorting using Optimal Transport

title: From RankNet to LambdaRank to LambdaMART

venue: An Overview. JMLR,

authors:
Sashank J. Reddi
Rama Kumar Pasumarthi
Aditya Krishna Menon
Ankit Singh Rawat
Felix X. Yu
Seungyeon Kim
Andreas Veit
Sanjiv Kumar

title: Rankdistil: Knowledge distillation for ranking

venue: In AISTATS,

authors:
Yining Wang
Liwei Wang
Yuanzhi Li
Di He
Wei Chen
Tie Yan Liu

title: A theoretical analysis of NDCG ranking

venue: measures. JMLR,

authors:
Sebastian Prillo
Julian Eisenschlos

title: Softsort: A continuous relaxation for the argsort operator

authors:
Yujia Xie
Hanjun Dai
Minshuo Chen
Bo Dai
Tuo Zhao

title: Differentiable top-k operator with optimal transport

venue: arXiv preprint arXiv:2002.06504,

authors:
Leonardo Rigutini
Tiziano Papini
Marco Maggini
Franco Scarselli

title: Sortnet: Learning to rank by a neural preference function

venue: IEEE transactions on neural networks,

authors:
Ziqiang Cao
Furu Wei
Li Dong
Sujian Li
Ming Zhou

title: Ranking with recursive neural networks and its application to multi-document summarization

authors:
Chenyan Xiong
Zhuyun Dai
Jamie Callan
Zhiyuan Liu
Russell Power

title: End-to-end neural ad-hoc ranking with kernel pooling

title: The analysis of permutations

venue: Applied Statistics, pages 193–202,

title: Individual choice behavior: A theoretical analysis

venue: Courier Corporation,

authors:
Yoshua Bengio
Nicholas Léonard
Aaron Courville

title: Estimating or propagating gradients through stochastic neurons for conditional computation

venue: arXiv preprint arXiv:1308.3432,

title: Gnu parallel - the command-line power tool

venue: ;login: The USENIX Magazine,

heading: 1 Introduction

text:
The goal of Learning-To-Rank (LTR) models is to rank a set of candidate items for any given search query according to a preference criterion [2]. The preference over items is specified via relevance labels for each candidate. The fundamental difficulty in LTR is that the downstream metrics of interest such as normalized discounted cumulative gain (NDCG) and average relevance position (ARP) depend on the ranks induced by the model. These ranks are not differentiable with respect to the model parameters, so the metrics cannot be optimized directly via gradient-based methods.
To resolve the above challenge, a popular class of LTR approaches map items to real-valued scores and then define surrogate loss functions that operate directly on these scores. Surrogate loss functions, in turn, can belong to one of three types. LTR models optimized via pointwise surrogates [3–6] cast ranking as a regression/classification problem, wherein the labels of items are given by their individual relevance labels. Such approaches do not directly account for any inter-dependencies across item rankings. Pairwise surrogate losses [7–14] can be decomposed into terms that involve scores of pairs of items in a list and their relative ordering. Finally, listwise surrogate losses [15–19] are defined with respect to scores for an entire ranked list. For many prior surrogate losses, especially those used for listwise approaches, the functional form is inspired via downstream ranking metrics, such as NDCG. However, the connection is loose or heuristically driven. For instance, SoftRank [14, 19] introduces a Gaussian distribution over scores, which in turn defines a distribution over ranks and the surrogate is the expected NDCG w.r.t. this rank distribution.
⇤This work was done prior to joining Amazon.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
We propose PiRank, a listwise approach where the scores are learned via deep neural networks and the surrogate loss is obtained via a differentiable relaxation to the sorting operator. In particular, we choose as building block the temperature-controlled NeuralSort [1] relaxation for sorting and specialize it for commonly used ranking metrics such as NDCG and ARP. The resulting training objective for PiRank reduces to the exact ranking metric optimization in the limit of zero temperature and trades off bias for lower variance in the gradient estimates when the temperature is high. Furthermore, PiRank scales to real-world industrial scenarios where the size of the item lists is very large but the ranking metrics of interest are determined by only a small set of top ranked items. Scaling is enabled by a novel divide-and-conquer strategy akin to merge sort, where we recursively apply the sorting relaxation to sub-lists of smaller size and propagate only the top items from each sub-list for further sorting.
Empirically, we benchmark PiRank against 5 competing methods on two of the largest publicly available LTR datasets: MSLR-WEB30K [20] and Yahoo! C14. We find that PiRank is superior or competitive on 13 out of 16 ranking metrics and their variants, including 9 on which it is significantly superior to all baselines, and that it is able to scale to very large item lists. We also provide several ablation experiments to understand the impact of various factors on performance. To the best of our knowledge, this work is the first to analyze the importance of training list size on an LTR benchmark. Finally, we provide an open-source implementation2 based on TensorFlow Ranking [21].

heading: 2 Background and Related Work

text: The LTR setting considers a finite dataset consisting of n triplets D = {qi, {xi,j}Lj=1, {yi,j}Lj=1}ni=1. The i-th triplet consists of a query qi 2 Q, a list of L candidate items represented as feature vectors xi,j 2 X , and query-specific relevance labels yi,j for each item j. The relevance labels yi,j can be binary, ordinal or real-valued for more fine-grained relevance. For generality, we focus on the real-valued setting. Given a training dataset D, our goal is to learn a mapping from queries and itemsets to rankings. A ranking ⇡ is a list of unique indices from {1, 2, . . . , L}, or equivalently a permutation, such that ⇡j is the index of the item ranked in j-th position. Without loss of generality, we assume lower ranks (starting from 1) have higher relevance scores. This is typically achieved by learning a scoring function f : Q ⇥ XL ! RL that maps a query context and list of candidate items to L scores. At test time, the candidate items are ranked by sorting their predicted scores in descending order. The training of f itself can be done by a suitable differentiable surrogate objective, which we discuss next.

heading: 2.1 Surrogate Objectives for LTR

text:
In this section, we briefly summarize prominent LTR approaches with a representative loss function for each category of pointwise, pairwise or listwise surrogate losses. We refer the reader to the excellent survey by [22] for a more extensive review. Omitting the triplet index, we denote the relevance labels vector as y 2 RL and an LTR model’s score vector obtained via the scoring function f as ŷ 2 RL. The simplest pointwise surrogate loss for ranking is the mean-squared error (MSE) between y and ŷ:
ˆ̀ MSE(y, ŷ) =
1
L
LX
i=1
(ŷi yi)2 . (1)
As the example loss above shows, pointwise LTR approaches convert ranking into a regression problem over the relevance labels and do not account for the relationships between the candidate items. Pairwise approaches seek to remedy this by considering loss terms depending in the predicted scores of pairs of items. For example, the widely used RankNet [9] aims to minimize the number of inversions, or incorrect relative orderings between pairs of items in the predicted ranking. It does so by modeling the probability p̂i,i0 that the relevance of the i-th item is higher than that of the i0-th item as a logistic map of their score difference, for all candidate items i, i0. The objective is then the
2https://github.com/ermongroup/pirank
cross-entropy:
ˆ̀ RankNet(y, ŷ) =
LX
i=1
LX
i0=1
(yi > yi0) log p̂i,i0 (2)
where (·) denotes the indicator function and p̂i,i0 is a function of ŷ. Pairwise approaches effectively model relationships between pairs of items and generally perform better than pointwise approaches, but still manifest limitations on downstream metrics which consider rankings in the full list and not just pairs. In fact, the larger the list of candidate items, the weaker these approaches tend to be: an error between the first and second item on a list is weighted the same in the RankNet loss as one between the last two items, despite the top items being of more importance in the LTR setting.
Listwise approaches learn from errors on the complete list. LambdaRank [13] extends RankNet by assigning weights to every loss term from Eq. 2:
ˆ̀ LambdaRank(y, ŷ) =
LX
i=1
LX
i0=1
`NDCG(i, i 0) log p̂i,i0 (3)
with `NDCG(i, i0) the difference in the downstream metric NDCG (defined below) when swapping items i and i0.

heading: 2.2 Ranking Metrics

text:
Downstream metrics operate directly on the predicted ranking ⇡̂ (obtained by sorting ŷ in descending order) and the true relevance labels y. They differ from conventional metrics used for other supervised learning problems in explicitly weighting the loss for each item by a suitably choosen increasing function of its predicted rank. For example, relevance position (RP) [23] multiplies the relevance labels with linearly increasing weights, and normalizes by the total relevance score for the query:
RP(y, ⇡̂) = PL j=1 y⇡̂j jPL j=1 yj
(4)
Averaging RP across the predictions made for all the queries in the test set gives the average relevance position (ARP) metric. Lower ARP signifies better performance.
A very common metric is the discounted cumulative gain (DCG) [24]. DCG computes the rescaled relevance of the j-th candidate by exponentiating its relevance label, and further divides it by the assigned log-ranking. This model incentivizes ranking models to focus on elements with higher graded relevance scores:
DCG(y, ⇡̂) = LX
j=1
2y⇡̂j 1 log2(1 + j)
(5)
A more common variant NDCG normalizes DCG by the maximum possible DCG attained via the optimal ranking ⇡⇤ (obtained by sorting y in descending order):
NDCG(y, ⇡̂) = DCG(y, ⇡̂)
DCG (y,⇡⇤) (6)
Higher DCG and NDCG signify better performance. Their truncated versions DCG@k and NDCG@k are defined by replacing L with a cutoff k in Eq. 5 so metrics are computed on the top-k items.
3 Scalable and Differentiable Top-k Ranking via PiRank
In PiRank, we seek to design a new class of surrogate objectives for ranking that address two key challenges with current LTR approaches. The first challenge is the gap between the downstream ranking metric of interest (e.g., NDCG, ARP) that involve a non-differentiable sorting operator and the differentiable surrogate function being optimized. The second challenge concerns the scalability w.r.t. the size of the candidate list L for each query item. Larger list sizes are standard
in industrial applications but present computational and memory challenges for current approaches during both training and test-time inference. Pairwise and listwise methods (or hybrids) typically scale quadratically in the list size L, the number of items to rank for each query. Combining surrogates for truncated metrics, such as LambdaRank in Eq. 3 with NDCG@k has a reduced complexity of O(kL) but comes at the cost of vanishing gradient signal from relevant entries below k (see Figure 1 for an illustration). Soft versions of the truncation metrics, such as Approximate NDCG Loss [25], can learn from all items but again scale quadratically with L or do not take advantage of GPU acceleration [26].
As defined previously, a ranking ⇡ is a list of indices equivalent to a permutation of {1, 2, . . . , L}. The set of possible rankings can thus be seen as the symmetric group SL, of size L!. Every permutation ⇡ can be equivalently represented as a permutation matrix P⇡ , an L⇥ L matrix such that its (i,⇡i)-th entry is 1 for all i 2 {1, 2, · · · , L} and the remaining entries are all 0. We define the sorting operator sort : RL ! SL as a map of an L-dimensional input vector to the permutation that corresponds to the descending ordering of the vector components. Prior work in relaxing the sorting operator is based on relaxation of its output, either in the form of rankings [19, 26, 27], or permutation matrices [1, 28–30]. PiRank first applies the latter kind of relaxations to the ranking problem by introducing a new class of relaxed LTR metrics, then introduces a new relaxation that is particularly suited to these metrics.

heading: 3.1 Relaxed Ranking Metrics

text:
We denote an LTR model by f✓ (e.g., deep neural network) with parameters ✓. The model outputs a vector of L scores ŷ = f✓(q,x1, . . . ,xL) for a query q and L candidate elements {xi}Li=1. We first consider the NDCG target metric. In Eq. 6, the numerator DCG(y, ⇡̂) involves computing ⇡̂ = sort(ŷ) which is non-differentiable w.r.t. ✓. Let g denote the column vector of graded relevance scores such that gj = 2yj 1. We can then rewrite DCG(y, ⇡̂) as:
DCG(y, ⇡̂) = LX
j=1
g⇡̂j
log2(1 + j) =
LX
j=1
[P⇡̂g]j log2(1 + j) . (7)
To obtain the DCG@k objective, one can replace L with k in the sum. We omit the suffix @k in the following, assuming that k has been defined, potentially equal to L which would yield the full metric.
Let bPsort(s)(⌧) denote a relaxation to the permutation matrix Psort(s) that can be used for differentiable sorting of an input score vector s, for some temperature parameter ⌧ > 0 such that the true matrix is recovered as ⌧ ! 0+. Since ⇡̂ = sort(ŷ), we can obtain a differentiable relaxation to DCG(y, ⇡̂):
[DCG(y, ŷ, ⌧) = kX
j=1
[ bPsort(ŷ)(⌧)g]j log2(1 + j) . (8)
Substituting this in the expression for NDCG in Eq. 6, we obtain the following relaxation for NDCG:
\NDCG(y, ŷ, ⌧) = [DCG(y, ŷ, ⌧) DCG(y,⇡⇤)
(9)
where the normalization in the denominator does not depend on ✓ and can be computed exactly via regular sorting. Finally, we define the PiRank surrogate loss for NDCG as follows:
`PiRank NDCG = 1 \NDCG(y, ŷ, ⌧) (10) which is bounded between 0 and 1 as is NDCG, and whose difference with the actual (1 NDCG) gets negligible as ⌧ ! 0+. Figure 2 illustrates the model architecture for the above objective. Similarly, we can derive a surrogate loss for the ARP metric in Eq. 4 as:
ˆ̀ PiRank ARP(y, ŷ, ⌧) =
Pk j=1[
bPsort(ŷ)(⌧)y]jj Pk
j=1 yj
. (11)

heading: 3.2 Example: Differentiability via NeuralSort

text:
Typically, relaxations to permutation matrices consider the Birkhoff polytope of doubly stochastic matrices. A doubly-stochastic matrix is a square matrix with entries in [0, 1] where every row and column sum to 1. In contrast, NeuralSort [1] is a recently proposed relaxation of permutation matrices in the space of unimodal row-stochastic matrices. A unimodal matrix is a square matrix with entries in [0, 1] such that the entries in every row sum to 1 (i.e. row-stochastic), but additionally enforce the constraint that the maximizing entry in every row should have a unique column index. See Figure 3 for an example of each type. Note that a unimodal matrix is not necessarily doubly-stochastic and vice versa. Permutation matrices are both doubly-stochastic and unimodal.
In NeuralSort [1], a unimodal relaxation of the permutation matrix Psort(ŷ) can be defined as follows. Let Aŷ denote the matrix of absolute pairwise score differences with i, j-th entry given as [Aŷ]ij = |ŷi ŷj |. Then, the i-th row of the relaxed permutation matrix is:
bP (NS)sort(ŷ)(⌧)i,· = softmax [((L+ 1 2i)ŷ Aŷ1)/⌧ ] (12)
where 1 is the vector with all components equal to 1. Its unimodal property makes it particularly well-suited to extracting top-k items because, as seen in Figure 3, taking the maximizing elements of the first k rows yields exactly k items but may yield less in the case of a doubly-stochastic relaxation. However, the complexity to obtain the top-k rows in this formulation, even for k as low as 1, is quadratic in L as the full computation of Aŷ1 is required for the softmax operation in Eq. 12. This is prohibitive when L k, a common scenario, and motivates the introduction of a new relaxation with a more favorable complexity for top-k ranking.

heading: 3.3 Scaling via Divide-And-Conquer

text:
Our PiRank losses only require the first k rows of the relaxed permutation matrix bPsort(ŷ). This is specific to the LTR setting in which only the top-ranked items are of interest, in contrast to the full sorting problem that requires the full matrix. In PiRank, we leverage this insight to construct a divide-and-conquer variant of differentiable sorting relaxations such as NeuralSort to reduce the complexity of the metric computation. Our proposed construction can be viewed as a relaxed and truncated multi-way merge sort algorithm with differentiable sorting relaxations as building blocks. In the following discussion, we use NeuralSort as our running example while noting that the analysis extends more generally to other differentiable relaxations as well.
Data Structure Construction. Let L = b1b2 · · · bd be a factorization of the list size L into d positive integers. Using this factorization, we will construct a tree of depth d with branching factor bj at height j. Next, we split the L-dimensional score vector ŷ into its L constituent scalar values. We set these values as the leaves of the tree. See Figure 4 for an example. At every other level of the tree, we will merge values from the level below into equi-sized lists. Let {kj}dj=0 be sizes for the intermediate results at level j, such that k0 = 1 (leaves) and min(k, kj 1bj)  kj  kj 1bj for j 1 (explained below). Then, in an iterative manner for levels j = 1, . . . , d, the value of a node at height j are the top-kj scores given by the application of the NeuralSort operator on the concatenation of the values of its children. With kd = k, the root value thus obtained is a relaxation of the top-k scores in ŷ. The top-k rows of the relaxed permutation matrix bPsort(ŷ) yielding these scores are constructed by compounding the operations at each iteration.
Computational Complexity. The intuition behind the favorable scaling is as follows. At step j, NeuralSort is applied on blocks of size kj 1bj as it merges bj sub-blocks of size kj 1. Obtaining the full sorted list of scores would require to keep all intermediate scores during the process, i.e., k
(max) j = b1 · · · bj = kj 1bj for j 1. In the last step, the NeuralSort operator is applied on a list of size kd 1bd, equal to L in this case, so the overall complexity would be at least quadratic in L as explained previously. However, since only the top-k scores are desired, intermediate outputs can be truncated if larger than k. Full truncation corresponds to k(min)j = min(k, kj 1bj). Any choice k
(min) j  kj  k (max) j is acceptable to recover the top-k scores, with larger values allowing more information to flow at the expense of a higher complexity. Choosing bj ⇡ L1/d and kj minimal, the list sizes bjkj 1 on which NeuralSort is applied at each step can thus be of the order of L1/dk, much smaller than L in the d > 1 and k ⌧ L scenario. Formally, let ⌧1, ⌧2, . . . , ⌧d be the relaxation temperatures at each height, with ⌧d = ⌧ and ⌧j  ⌧j+1 for j 2 {1, . . . , d 1}. Define the tensor Ŷ (0) by reshaping ŷ to shape (k0, b1, b2, . . . , bd), yielding components
Ŷ (0) 1,i1,i2,...,id = ŷ1+Pdj=1(ij 1) Qj 1 l=1 bl , (13)
with ij 2 {1, . . . , bj} and the first index is always 1 as k0 = 1. With the tree representation, the first tensor index is the position in the node value vector and the rest of the indices identify the node by the index of each branching starting from the root. For j 2 {1, 2, . . . , d}, recursively define the tensors Q̂(j), Ŷ (j) and P̂ (j) of respective shapes (kj , kj 1, bj , . . . , bd), (kj , bj+1, . . . , bd) and
(kj , b1, . . . , bd) with components
Q̂ (j) l,m,ij ,...,id
= softmax h⇣ (kj 1bj + 1 2l)Ŷ (j 1)m,ij ,...,id kj 1X
p=1
bjX
q=1
Ŷ (j 1)m,ij ,ij+1,...,id Ŷ (j 1) p,q,ij+1,...,id ⌘ /⌧j i ,
(14)
Ŷ (j) l,ij+1,...,id =
kj 1X
p=1
bjX
q=1
Q̂ (j) l,p,q,ij+1,...,id Ŷ (j 1) p,q,ij+1,...,id , (15)
P̂ (j) l,i1,...,id =
kj 1X
m=1
Q̂ (j) l,m,ij ,...,id P̂ (j 1) m,i1,i2,...,id , (16)
with P̂ (0) = 1. Intuitively, Ŷ (j) holds the relaxed top-kj scores at height j and Ŷ (d) is the desired top-k score vector. The interpretation of the indices in the tree structure is as for Ŷ (0), illustrated in Figure 4. More importantly, we keep track of the relaxed sorting operation that yielded this output. Q̂
(j) is the relaxed permutation matrix obtained by applying NeuralSort in Eq. 12 to Ŷ (j), while P̂ (j) compounds the relaxed permutation matrices obtained so far so it always maps from the initial list size. Finally, define the k ⇥ L matrix P̂ by reshaping the tensor P̂ (d), yielding components
P̂l,1+ Pd j=1(ij 1) Qj 1 l=1 bl = P̂ (d)l,i1,...,id , (17)
for ij 2 {1, . . . , bj}. The k rows of P̂ are used as the top-k rows of the relaxed sorting operator bPsort(ŷ)(⌧). This approach is equivalent to NeuralSort, yielding Eq. 12 for d = 1. Proof of convergence for ⌧ ! 0+ of this relaxation in the general case d 1 is presented in Appendix B. In the simple case where L = bd and we set bj = b, kj = min(k, bj) for all j 2 {1, . . . , d}, the complexity to compute P̂ and thus the PiRank losses is then O(L1+1/d + (d 1)k2L), which scales favorably in L if d > 1 and k = O(1). In the general case, the score list can be padded, e.g. to the power of 2 following L, such that the previous complexity holds for b = 2 and d = dlog2 Le, but other factorizations may yield lower complexity depending on L.

heading: 4 Experiments

text: We present two sets of experiments in this section: (a) benchmark evaluation comparing PiRank with other ranking based approaches on publicly available large-scale benchmark LTR datasets, and (b) ablation experiments for the design choices in PiRank.

heading: 4.1 Benchmark Evaluation via TF-Ranking

text:
Datasets. To empirically test PiRank, we consider two of the largest open-source benchmarks for LTR: the MSLR-WEB30K3 and the Yahoo! LTR dataset C144. Both datasets have relevance scores on a 5-point scale of 0 to 4, with 0 denoting complete irrelevance and 4 denoting perfect relevance. We give extensive details on the datasets and experimental protocol in Appendix C.
Baselines. We focus on neural network-based approaches and use the open-source TensorFlow Ranking (TFR) framework [21]. TFR consists of high-quality GPU-friendly implementations of several LTR approaches, common evaluation metrics, and standard data loading formats. We compare our proposed loss, PiRank-NCDG, with the following baselines provided by TensorFlow Ranking: Approximate NDCG Loss [25], Pairwise Logistic Loss (RankNet, Eq. 2), Pairwise Logistic Loss with lambda-NDCG weights (LambdaRank, Eq. 3), and the Softmax Loss. We also include NeuralSort, whose loss is the cross-entropy of the predicted permutation matrix. Of these methods, the Pairwise Logistic Loss (RankNet) is a pairwise approach while the others are listwise. While our scope is on differentiable ranking surrogate losses for training neural networks, other methods such as the tree-based LambdaMART [31] could potentially yield better results.
Setup. All approaches use the same 3-layer fully connected network architecture with ReLU activations to compute the scores ŷ for all (query, item) pairs, trained on 100,000 iterations. The maximum list size for each group of items to score and rank is fixed to 200, for both training and testing. Further experimental details are deferred to Appendix C. We evaluate Ordered Pair Accuracy (OPA), Average Relevance Position (ARP), Mean Reciprocal Rank (MRR), and NDCG@k with k 2 {1, 3, 5, 10, 15}. We determine significance similarly to [32]. For each metric and dataset, the best performing method is determined, then a one-sided paired t-test at a 95% significance level is performed on query-level metrics on the test set to compare the best method with every other method.
Results. Our results are shown in Table 1. Overall, PiRank shows similar or better performance than the baselines on 13 out of 16 metrics. It significantly outperform all baselines on NDCG@k for k 5 while Approx. NDCG is competitive on NDCG@k for k  3 and MRR. PiRank is also significantly superior on OPA and ARP metrics on Yahoo! C14 while NeuralSort is superior for MSLR-WEB30K.

heading: 4.2 Ablation Experiments

text:
Temperature. The temperature hyperparameter ⌧ is used in PiRank to control the degree of relaxation. We experiment on several values (⌧ 2 {0.1, 1, 5, 10}) using the MSLR-WEB30K dataset and the experimental settings for ablation provided in Appendix C. Figure 5 demonstrates the importance of correctly tuning ⌧ . High values (⌧ > 1) speed up training, especially in the early regime, while low values induce large gradient norms which are unsuitable for training and lead to the loss stalling or even diverging. Another observation is that the relaxed metric 1 ˆ̀PiRank NDCG@k
3https://www.microsoft.com/en-us/research/project/mslr/ 4https://webscope.sandbox.yahoo.com
closely follows the value of the downstream metric NDCG@k as expected. We further experimented with a very high temperature value and an exponentially decreasing annealing schedule in Appendix D.
Training List Size. The training list size parameter Ltrain determines the number of items to rank for a query during training. The setting is the same as for the temperature ablation experiment, but with training list sizes Ltrain 2 {10, 20, 40, 100} which we then evaluate on testing list sizes in the same range of values Ltest 2 {10, 20, 40, 100}. The dataset is again MSLR-WEB30K. Figure 6 exposes four patterns for NDCG@k. First, for a fixed Ltest and k, a larger Ltrain is always better. Second, for a fixed Ltest, we observe diminishing returns along k, as relative improvements decrease for all Ltrain. This observation is confounded by NDCG@k values growing larger with k, but the metric is always able to distinguish between ranking functions [33]. Third, for a fixed k, our returns along Ltest increase with Ltrain (except for Ltrain = 20 and k = 1). This means that the need for a larger Ltrain is more pronounced for larger values of Ltest. Fourth and last, the returns increase most dramatically with Ltrain when Ltest k (top left), a common industrial setting. Values for NDCG@k, MRR, OPA, ARP are provided in Appendix D. For MRR, using a larger Ltrain is always beneficial regardless of Ltest, but not always for OPA and ARP.
Depth. A main advantage of the PiRank loss is how it can scale to very large training list sizes Ltrain. This setting is difficult to come across with traditional LTR datasets, which are manually annotated, but occurs frequently in practice. One example is when the relevance labels are obtained from implicit signals such as clicks or purchases in recommendation systems. In this case, an LTR model is used to re-rank a list of candidates generated by another, simpler, model choosing among all possible items those potentially relevant to a query or context. An LTR model capable of handling very large lists can reduce the impact of errors made by the simpler candidate generation step, moving to the top an item lowly ranked at first that would have been cut off from a smaller list. To test the complexity shown in Section 3.2 in extreme conditions, we create a synthetic dataset as described in Appendix E. Figure 7 shows how the training time for depth d = 3 scales much more favorably than for d = 1, following their respective time complexities of O(L1+1/3) and O(L2).

heading: 5 Summary and Limitations

text:
We proposed PiRank, a novel class of surrogate loss functions for Learning-To-Rank (LTR) that leverages a continuous, temperature-controlled relaxation to the sorting operator [1] as a building block. This allows us to recover exact expressions of the commonly used non-differentiable ranking metrics in the limit of zero temperature, which we proved in particular for the NDCG metric. Crucially, we proposed a construction inspired by the merge-sort algorithm that permits PiRank to scale to very large lists.
In our experiments on the largest publicly available LTR datasets, we observed that PiRank has superior or similar performance with competing methods on the MSLR-WEB30K and Yahoo! C14 benchmarks on 13/16 ranking metrics and their variants.
As future work, we would like to explore other recent relaxations of the sorting operator [26, 34, 35] as a building block for the PiRank framework. Further, as ranking is a core component of modern day technology and influences everyday decision making pipelines involving vulnerable populations, care needs to be taken that our proposed systems are extended to account for biases and fairness criteria when deployed in real world settings.

heading: 6 Acknowledgements

text: Robin Swezey and Bruno Charron were supported by Rakuten, Inc. Stefano Ermon is supported in part from NSF (#1651565, #1522054, #1733686), ONR (N0001419-1-2145), AFOSR (FA9550-19-1-0024) and Bloomberg.

title: PiRank: Scalable Learning To Rank via Differentiable Sorting


summaries: # Overview  The paper proposes a framework incorporating deep reinforcement learning for resolving Ansatz optimization problems, which is with wide impacts on quantum chemistry. The authors have a good introduction and related work section, which covers most standing works in quantum reinforcement learning and variational circuit learning.   Compared with Rotosolve and COBYLA, the proposed DDQN-based method attains state-of-the-art results on estimating the ground-state energy of lithium hydride.  Overall, I like the idea but the baseline comparison and some time complexity could better incorporate to add the depth of this paper. The current version is more application-oriented and less novel as a general ML framework considering existing works in the neural architecture search (NAS) community.   - Justification of DDQN and comparison   When discussing "why selecting DDQN for the RL", there is very little discussion.   Since this work is not the first works on applying the heuristic method for quantum circuit architectures search (QCAS), the contribution is more on framing the Ansatz optimization and the benchmark results. It would be more valuable to address the selection and justification of the algorithm. (e.g., DRL-based vs Neuroevolution-based or at least the variants inside DQNs)  For the general audience in the NeurIPS community, instead of only showing the DDQN-based method for QCAS, providing more in-depth discussion between variants of the DRL algorithm (e.g., DQN, DQN with dueling, DDQN with dueling) and its complexity could gain better values of this paper.

summaries: The variational quantum eigensolver (VGE) is a method that utilizes a Noisy Intermediate Scale Quantum (NISQ) computer to find the ground state of quantum systems. At its core, an Ansatz for the ground-state wave-function is parameterized in terms of a quantum circuit, i.e. a series of single-qubit and two-qubit gates acting on a reference state, and the optimal parameters of the circuit are determined by a classical algorithm that uses the NISQ to evaluate the performance (energy) of the Ansatz.In this manuscript, the authors propose a reinforcement learning (RL) based approach to identify the small circuits (i.e. with the low number of gates, and thus less prone to errors) that still allow to reach chemical accuracy. The RL method is based on double deep-Q learning and curriculum learning. The authors employ their method to find the ground state energy of LiH approximating the electronic Hamiltonian as a 4 or 6 qubits Hamiltonian. For 3 different bond distances, the method proposed by the authors identifies circuits that achieve chemical accuracy, but whose size is lower as compared to other Ansatze

summaries: This paper studies the ansatz for Variational Quantum Eigensolver (VQE) quantum circuits. The authors propose a deep reinforcement learning framework to generate the ansatz for VQE circuit, aiming to achieve low estimated energy and shallow circuit depth. The authors leverage curriculum learning to gradually reduce the energy threshold (increase difficulty) to avoid learning failure. The method is evaluated on LiH molecule in different settings and shows shallower circuit than baseline HE and UCCSD circuits.

summaries: This work demonstrates that reinforcement learning with intrinsic motivation can be effectively used to search over the space of ansatzes for the variational quantum eigensolver (VQE) algorithm. This algorithm is used in quantum chemistry to approximate the ground state energy of molecules (e.g. LiH). The author(s) describe how DDQN trained with Adam can learn to optimize a VQE-relevant reward function, in an environment which runs an optimization subroutine (COBYLA or rotosolve) at each step to optimize the rotation angles of the ansatz's gates. Their LiH experiments used a simulated noiseless quantum environment, and they benchmarked the performance against two well-known ansatzes. The results show that in simulation, RL has promising potential for circuit depth improvement.

abstractText: The study of Variational Quantum Eigensolvers (VQEs) has been in the spotlight in recent times as they may lead to real-world applications of near-term quantum devices. However, their performance depends on the structure of the used variational ansatz, which requires balancing the depth and expressivity of the corresponding circuit. At the same time, near-term restrictions limit the depth of the circuit we can expect to run. Thus, the optimization of the VQE ansatz requires maximizing the expressivity of the circuit while maintaining low depth. In recent years, various methods for VQE structure optimization have been introduced but the capacities of machine learning to aid with this problem have not yet been extensively investigated. In this work, we propose a reinforcement learning algorithm that autonomously explores the space of possible ansatzes, identifying economic circuits which still yield accurate ground energy estimates. The algorithm uses a feedback-driven curriculum learning method that autonomously adapts the complexity of the learning problem to the current performance of the learning algorithm and it incrementally improves the accuracy of the result while minimizing the circuit depth. We showcase the performance of our algorithm on the problem of estimating the ground-state energy of lithium hydride (LiH) in various configurations. In this well-known benchmark problem, we achieve chemical accuracy and state-of-the-art results in terms of circuit depth.

title: Quantum computing in the NISQ era

venue: and beyond. Quantum,

authors:
Alberto Peruzzo
Jarrod McClean
Peter Shadbolt
Man-Hong Yung
Xiao-Qi Zhou
Peter J Love
Alán Aspuru-Guzik
Jeremy L

title: O’brien. A variational eigenvalue solver on a photonic quantum processor

venue: Nature Communications,

authors:
Abhinav Kandala
Antonio Mezzacapo
Kristan Temme
Maika Takita
Markus Brink
Jerry M Chow
Jay M Gambetta

title: Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets

authors:
Harper R. Grimsley
Sophia E. Economou
Edwin Barnes
Nicholas J. Mayhall

title: An adaptive variational algorithm for exact molecular simulations on a quantum computer

authors:
Ho Lun Tang
V.O. Shkolnikov
George S. Barron
Harper R. Grimsley
Nicholas J. Mayhall
Edwin Barnes
Sophia E. Economou

title: qubit-ADAPT-VQE: An adaptive algorithm for constructing hardware-efficient ansatze on a quantum processor

authors:
Pierre-Luc Dallaire-Demers
Nathan Killoran

title: Quantum generative adversarial networks

venue: Phys. Rev. A,

authors:
Marcello Benedetti
Erika Lloyd
Stefan Sack
Mattia Fiorentini

title: Parameterized quantum circuits as machine learning models

venue: Quantum Science and Technology,

authors:
Leo Zhou
Sheng-Tao Wang
Soonwon Choi
Hannes Pichler
Mikhail D. Lukin

title: Quantum approximate optimization algorithm: Performance, mechanism, and implementation on nearterm devices

venue: Phys. Rev. X,

authors:
Jonathan Romero
Alán Aspuru-Guzik

title: Variational quantum generators: Generative adversarial quantum machine learning for continuous distributions

venue: Advanced Quantum Technologies,

authors:
M.-H. Yung
J. Casanova
A. Mezzacapo
J. McClean
L. Lamata
A. Aspuru-Guzik
E. Solano

title: From transistor to trapped-ion computers for quantum chemistry

venue: Scientific Reports,

authors:
Abhinav Kandala
Antonio Mezzacapo
Kristan Temme
Maika Takita
Markus Brink
Jerry M. Chow
Jay M. Gambetta

authors:
Marcello Benedetti
Mattia Fiorentini
Michael Lubasch

title: Hardware-efficient variational quantum algorithms for time evolution, 2020

title: Learning and development in neural networks: the importance of starting small

authors:
Yoshua Bengio
Jérôme Louradour
Ronan Collobert
Jason Weston

title: Curriculum learning

venue: In ACM International Conference Proceeding Series,

authors:
IG Csizmadia
BT Sutcliffe
MP Barnett

title: A group orbital study of lithium hydride

venue: Canadian Journal of Chemistry,

authors:
Steven Herbert
Akash Sengupta

title: Using reinforcement learning to find efficient qubit routing policies for deployment in near-term quantum computers

venue: arXiv preprint arXiv:1812.11619,

title: Quantum logic gate synthesis as a markov decision process

venue: arXiv preprint arXiv:1912.12002,

authors:
Mohammad Pirhooshyaran
Tamas Terlaky

title: Quantum circuit design search

venue: arXiv preprint arXiv:2012.04046,

authors:
Thomas Fösel
Murphy Yuezhen Niu
Florian Marquardt
Li Li

title: Quantum circuit optimization with deep reinforcement learning, 2021

authors:
Shi-Xin Zhang
Chang-Yu Hsieh
Shengyu Zhang
Hong Yao

title: Neural predictor based quantum architecture search

venue: arXiv preprint arXiv:2103.06524,

authors:
En-Jui Kuo
Yao-Lung L Fang
Samuel Yen-Chi Chen

title: Quantum architecture search via deep reinforcement learning

venue: arXiv preprint arXiv:2104.07715,

authors:
Yuxuan Du
Tao Huang
Shan You
Min-Hsiu Hsieh
Dacheng Tao

title: Quantum circuit architecture search: error mitigation and trainability enhancement for variational quantum solvers

authors:
Arthur G. Rattew
Shaohan Hu
Marco Pistoia
Richard Chen
Steve Wood

title: A domainagnostic, noise-resistant, hardware-efficient evolutionary variational quantum eigensolver

venue: arXiv: Quantum Physics,

authors:
D Chivilikhin
A Samarin
V Ulyantsev
I Iorsh
AR Oganov

title: Kyriienko. Mog-vqe: Multiobjective genetic variational quantum eigensolver

venue: arXiv preprint arXiv:2007.04424,

authors:
Nikolaus Hansen
Andreas Ostermeier

title: Completely derandomized self-adaptation in evolution strategies

venue: evol. Comput.,

authors:
M Bilkis
M Cerezo
Guillaume Verdon
Patrick J Coles
Lukasz Cincio

title: A semi-agnostic ansatz with variable structure for quantum machine learning

venue: arXiv preprint arXiv:2103.06712,

authors:
Volodymyr Mnih
Koray Kavukcuoglu
David Silver
Alex Graves
Ioannis Antonoglou
Daan Wierstra
Martin Riedmiller

title: Playing atari with deep reinforcement learning

venue: In NIPS Deep Learning Workshop

title: A direct search optimization method that models the objective and constraint functions by linear interpolation

venue: In Advances in optimization and numerical analysis,

authors:
Mateusz Ostaszewski
Edward Grant
Marcello Benedetti

title: Structure optimization for parameterized quantum circuits

authors:
Rémy Portelas
Cédric Colas
Lilian Weng
Katja Hofmann
Pierre-Yves Oudeyer

title: Automatic Curriculum Learning For Deep RL: A Short Survey

venue: IJCAI International Joint Conference on Artificial Intelligence,

authors:
Jacob T. Seeley
Martin J. Richard
Peter J. Love

title: The bravyi-kitaev transformation for quantum computation of electronic structure

venue: The Journal of Chemical Physics,

authors:
P. Jordan
E. Wigner

title: Über das paulische äquivalenzverbot

venue: Zeitschrift für Physik,

authors:
R.S. Sutton
A.G. Barto

title: Reinforcement Learning: An Introduction

authors:
Yasunari Suzuki
Yoshiaki Kawase
Yuya Masumura
Yuria Hiraga
Masahiro Nakadai
Jiabao Chen
Ken M Nakanishi
Kosuke Mitarai
Ryosuke Imai
Shiro Tamiya

title: Qulacs: a fast and versatile quantum circuit simulator for research

authors:
Mark R. Hoffmann
Jack Simons

title: A unitary multiconfigurational coupled-cluster method: Theory and applications

authors:
Marco Cerezo
Andrew Arrasmith
Ryan Babbush
Simon C Benjamin
Suguru Endo
Keisuke Fujii
Jarrod R McClean
Kosuke Mitarai
Xiao Yuan
Lukasz Cincio

title: Variational quantum algorithms

heading: 1 Introduction

text:
As we are entering the so-called Noisy Intermediate Scale Quantum (NISQ) [1] technology era, the search for more suitable algorithms under NISQ restrictions is becoming ever more important. A truly compatible NISQ application must first be amenable to architecture constraints and size limits. Furthermore, to minimize the adverse effects of gate errors and decoherence, it is important that the circuits are as gate-frugal and as shallow as possible.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
Perhaps the most promising classes of such algorithms are based on variational circuit methods, with which we have high expectations when applied to problems in quantum chemistry. A key problem in this field is the computing of ground state energies and low energy properties of chemical systems (the chemical structure problem). This problem is believed to be intractable in general, yet the quantum Variational Quantum Eigensolver (VQE) [2] algorithm can provide solutions in regimes which lie beyond the reach of classical algorithms, while maintaining NISQ-friendly properties [3, 4].
VQE is a hybrid quantum-classical algorithm, where a parametrized quantum state is prepared on a quantum computer, the parameters of which are selected using classical optimization methods.
The objective is to prepare the state |ψ(~θ)〉 which can be used to approximate the ground state of a given Hamiltonian H by the variational principle
Emin ≤ min ~θ (〈ψ(~θ)|H|ψ(~θ)〉) , (1)
where Emin is the true ground state energy of H . The parametrized state is prepared by applying U(~θ), which is a parametrized quantum circuit (typically with a fixed architecture), where the angles ~θ = (θ1...θn) specify the rotation angles of the local unitary rotations present in the circuit. This circuit, known as the ansatz is applied to an initial state |ψ0〉, usually chosen to be the fiducial “all zero” state |00...0〉, to prepare the state |ψ(~θ)〉 = U(~θ)|ψ0〉. It is well established that the structure of the ansatz can dramatically influence the VQE’s performance [4, 5], as the closeness of the estimated ground state to the true one depends on the state manifold accessible by the ansatz. Thus finding new architecture construction methods could lead to breakthroughs in quantum variational methods for chemistry (e.g. for strongly-correlated systems, for which standard ansatzes might fail), but also in other domains which utilize variational circuits such as machine learning and optimization [6, 7, 8, 9].
Currently, the foremost ansatzes fall primarily in two classes: chemistry-inspired (e.g. the unitary coupled-cluster ansatz [2, 10]) and hardware-inspired (e.g. the hardware efficient ansatz [11]). Architectures from both of these classes entail using a fixed architecture [2, 10, 11, 12] determining the unitary U(~θ), and hence the corresponding ansatz. The ansatz circuit is then usually decomposed into two-qubit CNOT and one-qubit rotation gates parametrized by (θ1, θ2, . . . , θn) ∈ [0, 2π]n to be optimized by a classical subroutine. However, the architecture itself can also be optimized. This results in a hard structure optimization problem, as it is a combinatorial optimization problem that must balance two competing factors. On the one hand, the ansatz needs to be expressive enough to guarantee a good approximation of the ground state energy. On the other hand, the depth and size of the circuit need to be controlled in order for the latter to be compatible with NISQ restrictions.
Contributions In this work, we propose a general optimization procedure for VQE based on deep reinforcement learning (RL) which is designed to yield quantum circuits that are both gate and depth-efficient. We supplement this RL approach with curriculum learning [13, 14], a powerful machine learning method for solving complex problems by leveraging the solutions of previouslysolved simpler instances. Specifically, we introduce a feedback-driven curriculum learning method that autonomously adapts the complexity of the learning problem to the current performance of the learning algorithm. We apply our architecture to the well-established benchmarking problem of finding the ground state energy of the LiH molecule [15, 3] and observe chemical accuracy while maintaining a low-depth quantum circuit and achieving state-of-the-art results in terms of gate efficiency. Apart from ground state estimation, the proposed method has a wider range of applications, the algorithm can be applied to any variational-circuit-based algorithm.
The rest of the paper is organized as follows. In Section 2, we discuss the related works. In Section 3, we introduce our method with simplistic assumptions about the exact value of the ground state energy. At the end of this section, we provide a method circumventing this unrealistic requirement. As an initial proof-of-concept, in Section 4, we present the results assuming access to the exact value of energy. In Section 5, we provide the results for the full method that utilizes a rough proxy of energy obtained with classical methods. We conclude the paper with a discussion of possible future directions.

heading: 2 Related Work

text: The automatic construction of quantum circuits with the use of heuristics/machine learning methods is a topic that has recently been gaining more attention [16, 17, 18, 19, 20]. In the recent article [21], the authors explore various methods of deep reinforcement learning for quantum architecture search. In contrast to our approach the authors generate circuits which are designed to prepare multi-qubit GHZ states. Several works concern the construction of quantum circuits in the context of quantum chemistry. In [22] the authors propose the Quantum Architecture Search algorithm, based on the AutoML method – Neural Architecure Search, which is benchmarked on the H2 molecule – a simpler system than LiH. On the other hand, more complex molecules are considered in [23], the authors use evolutionary algorithms to optimize the structure of VQE circuits for quantum chemistry and combinatorial optimization. The gate set in this algorithm is composed of one-qubit universal gates and two-qubit controlled universal gates, which after the optimization procedure, are decomposed into CNOT gates and one-qubit universal rotation gates. Another evolutionary strategy was explored in [24], where a multi-objective genetic algorithm is used to optimize the structure of the VQE ansatz in the context of quantum chemistry problems. The topology of the circuits is optimized by a non-dominated sorting genetic algorithm while the parameters are globally tuned by Covariance Matrix Adaptation Evolution Strategy (CMA-ES) [25]. Yet another different approach, explored in the manuscript [26], involved applying a set of rules to both grow and remove quantum gates during the optimization. The last three manuscripts focus on solving problems in quantum chemistry by constructing the shortest possible quantum circuits.

heading: 3 Methods

text: In this section, we discuss our approach for constructing VQE ansatzes using RL. We discuss the state and action representations, as well as the reward function used in this work. We then introduce a novel adaptation of curriculum learning applied to VQE circuit construction with different parameter optimization strategies.

heading: 3.1 Ansatz optimization as a reinforcement learning problem

text:
We describe ansatz optimization as a reinforcement learning environment, where the states encode the current circuit. The actions encode a gate that is added to the current circuit. The environmental transitions are deterministic because the subsequent state is defined by the previous state appended by the taken action. At each time step t, the agent receives the reward R according to the following formula:
R =  5 if Et < ξ −5 if t ≥ L and Et ≥ ξ max ( Et−1−EtEt−1−Emin ,−1) otherwise , (2)
The goal of the agent is to reach the minimal energy Emin within a predefined threshold ξ. The energy Et is calculated for the current circuit representing the quantum state |ψ(~θ)〉 according to:
Et = 〈ψ(~θ)|H|ψ(~θ)〉, (3) where ~θ describes the angles of the rotation gates. The vector ~θ needs to be separately optimized to obtain the reward R. This optimization subroutine is a crucial hyperparameter of this RL environment and it is explained in more detail in the following two sections. The details on the reward shaping are discussed in Supplementary Materials.
We utilize deep RL methods, thus the states and actions are represented in a neural network-friendly form. Namely, each state is represented as an ordered list of layers that are composed of single quantum gates. Thus the environmental state, which is represented by this list, fully describes the whole circuit (with a specified gate ordering). For constructing the circuits, we use CNOT and one qubit rotation gates – which are realizable on currently available quantum devices. The CNOT gates are encoded by two values indicating position of control and target qubits (the position is enumerated starting from 0). The rotation gates are encoded by two integers (starting from 0). The first number indicates the qubit register and the second specifies the axis of rotation (X – 1, Y – 2, Z – 3). We deliberately omit the continuous parameters describing the angles of the rotation gates from the state representation. Instead, the energy estimated for the state is appended to state representation. The
user needs to define the maximum number of circuit layers (L). If a given circuit has fewer layers than L, the remaining ones are filled with identity operators (c.f. Fig. 1). The agent constructs the circuit iteratively, starting from an empty list, and adding a single quantum gate at the end of the current circuit. This way the agent starts each episode with exactly the same conditions, i.e. an empty state, avoiding an additional source of randomness tied to the initial state. Thus, the set of all possible actions is equivalent to the set of all possible quantum gates that the agent can select. The size of the set of all possible actions for the agent is then 3|Q|+2 (|Q| 2 ) = |Q|(|Q|+2), where |Q| is
the number of qubits. The agent can choose from 3|Q| single-qubit gates and from 2 (|Q|
2
) two-qubit
gates. We use a simple one-hot encoding for the actions.

heading: 3.2 Specification of the agent and the environment

text:
We employ a Double Deep-Q network [27] (DDQN) with an -greedy policy and an ADAM optimizer for better stability. More technical details about the Reinforcement Learning procedure are described in the Experiments section (Section 4). As described in the previous section, to obtain a reward R for each circuit, an optimization subroutine needs to be applied to determine the continuous values of the rotation gate angles. We use well-developed methods for continuous optimization such as Constrained Optimization By Linear Approximation (COBYLA) [28] and Rotosolve [29]. Whilst we could use an agent for this purpose as well, we abstain from doing so for two main reasons. Firstly, in this work, we aim at assessing the efficacy of RL for circuit structure optimization, rather than for parameter searching. The latter is investigated extensively in other literature and thus treated as a separate subroutine that can be solved by other, more developed, tools. The second reason is practical, as training the agent to reliably predict values of angles would result in significantly longer training periods.
For the above reasons, our approach is hybrid: the agent learns how to, and is rewarded for, constructing particular circuits given a set of parameters determined by an independent optimization algorithm. We apply the angle optimization subroutine only after the steps in which the agent appends a rotation gate to the circuit, thus eliminating the necessity of including the parameters in the state representation. The number of angles optimized at a given step is a hyperparameter in our method, the choice of which will be analyzed in Sec. 4.2. In this work, we consider optimizing all angles at once (global strategy), as well as optimizing a few angles at a time (local strategy) . These different experimental settings allow us to check whether the rough energy approximation obtained from only optimizing a subset of the circuit angles is sufficient to create sufficiently good circuits.

heading: 3.3 Feedback-driven curriculum learning

text:
As explained, the agent is rewarded for creating circuits that pass a given threshold. In our experiments, we set the threshold to so-called chemical accuracy, which corresponds to an energy that differs from the ground state energy by less than 0.0016 Hartree. Even in cases where the exact value of minimum energy is known, setting the value of threshold ξ directly to chemical precision from the beginning of the training may result in the agent failing due to poor exploration. A possible solution is to introduce the agent to tasks of increasing difficulty known as curriculum learning [13] which was found to be beneficial for neural network training [14]. However, this approach requires the user to design a task sequence which, without a priori knowledge of the relationship between
the threshold value and the corresponding task difficulty, may lead to the agent reaching undesired local minima.1
Inspired by the body of works exploring automatic curriculum learning reviewed in RL [30], we propose a feedback-driven curriculum learning method in which the difficulty of the current task is dynamically adjusted based on the current performance of the agent. Hence, the agent does not rely on a human-defined task schedule and builds its knowledge gradually paced by the agent’s performance. The proposed method, illustrated in Fig. 2, starts with an arbitrary threshold ξ1 that is decreased according to two rules. The first rule decreases the threshold greedily to the best energy obtained so far ξ2 after each G episodes. Additionally, the amortization factor δ is added to the threshold at the moment of a greedy shift and each time the agent fails to solve multiple consecutive episodes. To gradually decrease the amount of added amortization δ, after a few successful episodes we decrease the amortization δ by a certain factor until the agent reaches the energy that was greedily obtained at first. Since in this feedback-driven curriculum learning method the threshold is successively decreased, we will also refer to this approach as moving threshold.
Note that due to the dynamic nature of our reward system we can substitute the true value of Emin, which is in practical cases unknown, with an arbitrary value α that is lower than minimum energy Emin and set a threshold ξ to a value that guarantees that the exact energy falls into the range Emin ∈ (α, α+ ξ). Note that, in principle, the method does not pose any restrictions on the starting threshold and the agent can start learning from any point, so we can set the ξ arbitrarily big to make sure that the Emin is in the range. The α value can also be set in the same vein, however, a simple method to roughly estimate the lower bound of energy can be utilized instead. If the agent is able to create circuits with chemical precision relative to any (reasonably) higher energy, the training with ever-increasing difficulty will ultimately lead to the chemical accuracy without computing the exact energy. Experiments proving the validity of this argument are presented in Section 4.2.

heading: 4 Experiments

text: We start this section with a description of the chemical problems on which we evaluate the proposed approach. Next, we will describe the experimental setup and present our results.

heading: 4.1 Experimental setup

text:
In our analysis of RL for VQE circuit synthesis, we focus on the problem of finding the ground state energy of the lithium hydride (LiH) molecule for various intramolecular distances, as well as Hamiltonians on differing qubit numbers, which stem from different approximations of the true chemical problem. All experiments are divided into two parts. In the first part, we explain how the choice of optimizer and number of optimized parameters per step impact the performance of the RL
1We tested multiple hard-coded schedules for shifting the threshold. However, the algorithm did not pass the desired lowest threshold while using these pre-defined sequences of thresholds.
approach. This part is evaluated on less challenging problem instances, i.e. with a smaller quantum system, action space, and state space. The second part, on the other hand, will be performed on the same molecule but simulated on a higher dimensional system. We assume that the number of measurements is sufficiently large that sampling noise is negligible. Whilst this is a significant assumption to make, and a current limitation of our method, in this work we are interested in a proof of concept for RL-based circuit synthesis. Thus we do not include the additional overhead incurred by finite measurements, which is left for future work.
Quantum chemistry problems. As mentioned earlier, in this work we focus on finding the ground state energy of the LiH molecule, although our approach design is not limited to this molecule. The Hamiltonians are computed in STO-3G basis. In the first part of our analysis, we consider a simpler approximation of LiH molecule which, after taking into account the symmetry of the molecule and removing the orbitals with weak interaction, results in a Hamiltonian defined on 4 qubits. Thus, the state space and action space are significantly smaller than the ones for the full LiH Hamiltonian. In this model, we utilize the parity mapping to convert molecular Hamiltonian to qubit Hamiltonian [31]. We examine proposed method on three values of LiH bond distances, 1.2Å, 2.2Å and 3.4Å. In the second experiment, we use the larger Hamiltonian which only takes into account the symmetry of the molecule, and is therefore defined on 6 qubits, for which we use the Jordan-Wigner mapping [32]. We opted to switch from the parity to the Jordan-Wigner mapping when considering the 6 qubit Hamiltonian in order to compare our results with previous literature which tackled this problem using a different approach [23]. We only focus on a single geometry for this case, i.e. for bond distance 2.2Å. All Hamiltonians were generated using the Qiskit library [33].
Implementation details.2 In all experiments we utilize n-step DDQN algorithm, with the discount factor set to γ = 0.88, and the probability of a random action being selected is set by an ε−greedy policy, with ε decayed in each step by a factor of 0.99995 from its initial value = 1, down to a minimal value ε = 0.05. The memory replay buffer size is set to 20,000. The target network in the DDQN training procedure is updated after every 500 actions. After each training episode, we included a testing phase where the probability of random action is set to = 0 and the experience replay procedure is turned off, i.e. the experiences obtained during the testing phase are not included in the memory replay buffer.
In our experiments, we use differing step sizes in the n-step trajectory rollout updates [34], which specify exactly how the Q-function approximations are updated. This hyperparameter of the model is set to n = 1 for the first part of the experiments. The reported results correspond to the experiment performed with the value n = 6. In the moving threshold approach, the threshold is changed greedily after 2000 episodes with an amortization radius of 0.0001. After 50 successfully solved episodes, the amortization radius is decreased by 0.00001. The initial threshold value is set to ξ = 0.005. Simulations of quantum circuits were performed using Qulacs library [35] (MIT License). The hyperparameters were selected through coarse grain search. The employed network is a fully connected network with 5 hidden layers with 1000 neurons each for the 4-qubit case and 2000 neurons each for the 6-qubit case. The maximal number of gates is equal to 40. All experiments were performed on three computing clusters - 4 Titan RTX GPUs, 4 Titan V GPUs, and 4 Tesla V100 GPUs.
Evaluation. To validate the capabilities of the reinforcement learning approach we compare it with well-established architectures, namely the Hardware Efficient (HE) [11] ansatz and UCCSD [36, 37] ansatz. The number of layers of the HE ansatz is tailored to each Hamiltonian considered. We report the smallest number of layers for which we have achieved chemical accuracy using our chosen optimizers. Moreover, the naive approach of UCCSD is used, and it is likely possible to find a shallower implementation of this ansatz, but for the purposes of this manuscript, it is an acceptable benchmark.
In all experiments, we compare the minimal depth and the number of gates of the obtained circuits (for more details see Supplementary Materials). By depth, we mean the length of the longest path between input and the output along qubit wires, without taking into account quantum gate dependency. Each RL experiment runs on 10 trials, i.e. experiments run on 10 different random seeds. For the first part of experiments, we consider two optimization methods: Rotosolve and COBYLA.
2The code is available on https://github.com/mostaszewski314/RL_for_optimization_of_VQE_ circuit_architectures
Both of these optimization methods can be applied with a local strategy, where the optimizer updates the last five rotation gates after each agent step, or a global strategy, where after each time step a full update is performed. For the local optimization strategy, we set the number of available iterations of Rotosolve to 5, whilst for the global strategy, the number of iterations is chosen to be 25. By iterations (for Rotosolve) we mean one complete cycle updating all the parameters under consideration. We chose 100 iterations for COBYLA for both strategies. Due to the fact that the number of iterations is fixed, convergence is not always guaranteed. However, in most cases, these values were sufficient and more iterations did not improve the energy estimate.
In the LiH 4-qubit experiments, we were able to establish the strategy and the optimizer to use in the LiH experiments with 6-qubits. For the setup with 6-qubit, we chose global optimization in each step and COBYLA with 200 iterations.

heading: 4.2 Results

text:
LiH - 4-qubit - different bond distances. In this section, we discuss the results of the LiH experiments with 4 qubits. In Fig. 3, the depth (left) and the total number of gates (right) of the circuits which achieve chemical accuracy are presented, with the average taken over the minimal values from the different trials. For bond distances 1.2Å and 2.2Å, the agent proposed quantum circuits that were shallower and contained fewer gates than the standard approaches, in every trial. For bond distance 3.4Å, the agent using local COBYLA optimization found quantum circuits satisfying chemical accuracy in 2 out of 10 trials, whereas the agent using local Rotosolve did so in 3 out of 10 trials. On the other hand, when using global optimization, the agent found circuits satisfying chemical accuracy in every trial, regardless of the optimizer used. In almost all cases, the average minimal depth and gate count were less than those obtained using standard approaches, i.e. HE and UCCSD, the exception being when the agent used local Rotosolve, which resulted in circuits deeper than the HE ansatz. Given the above results, COBYLA seems to outperform Rotosolve for this task. Moreover, taking into account the number of successful trials, we conclude that our approach is significantly improved when all angles are optimized.
LiH - 6-qubits - moving threshold. In this section, we discuss the results of the LiH experiments with 6 qubits. We evaluated the fixed threshold approach on the 6-qubit LiH Hamiltonian case,
which, however, did not give any positive results. The experiments where global optimization after each step was used did not yield any circuits achieving chemical accuracy. This seems to stem from the reward function with the chemical accuracy threshold being too sparse. Whilst gradually decreasing the threshold is the obvious next step, we opted for the curriculum learning approach based on the moving thresholds, in order to decrease the threshold automatically rather than manually. As one can see in Table 1, curriculum agents provide better results than standard approaches. To the best of our knowledge, the only previous work tackling this problem for the 6 qubit LiH Hamiltonian is [23]. Whilst we cannot quantitatively compare our results with their work due to differing gate compilations, we note out that our approach seems to generate circuits roughly 5 times shallower than the ones obtained in [23].
By looking closely at how the moving threshold guides the agent in the direction of chemical accuracy, we can analyze the mean difference between the exact energy and the energy estimate using the agent’s circuit from the end of each episode. In Fig. 4 we plot this error for a particular case at different scales to understand better what happens at different training stages. The blue dots represent the error in the agent energy estimates, whilst the orange curve represents the moving threshold. The left of Fig. 4 shows this error for the entire training period but does not provide much information due to the large deviation in the error. On the other hand, in the right plot of Fig. 4, we focus more on episodes which resulted in errors closer to chemical accuracy. The agent is guided by a decreasing moving threshold, with the threshold occasionally increasing abruptly due to amortization, which helps the agent adapt to a new lower threshold.

heading: 5 Learning procedure with lower-bound approximation to the ground-state energy

text:
So far we have relied on the assumption that the agent uses the energy error with respect to the exact solution as a learning metric. This assumption in practice is of course not reasonable, as estimating the energy to this precision is the main objective of VQE algorithms to start with. One way to relax the assumption of knowing the exact energy is to provide reasonable information about the lower and upper bounds, and classical and cheaper methods, respectively, and which incurs only a logarithmic overhead in the precision by using a binary search for the best achievable energy. Another solution stems from our moving threshold approach.
The moving threshold approach discussed in the previous sections not only allows us to solve more demanding problems, like the 6-qubit Hamiltonian but also removes the requirement of knowing the exact energy. In order to demonstrate this method, we performed an additional experiment on the 4- qubit LiH Hamiltonian at bond distance 2.2Å. Instead of using the exact energy, i.e. ≈ −7.8448Ha, we used the negative sum of the absolute values of the Hamiltonian’s Pauli coefficients, i.e. for a HamiltonianH = ∑M j=1 cjPj , we take− ∑M j=1 |cj | to guide the agent. This is an example of a very rough easy-to-compute lower bound on the energy but requires the Hamiltonian to be local. For this LiH geometry, this weight sum evaluates to −10.0604Ha. We set the amortization radius to 0.005, the number of episodes after greedily shifting the threshold to 500, and the amortization radius is decreased after every 25 successfully solved episodes. The initial threshold value we set to ξ = 4. We used global COBYLA with 100 iterations to optimize the angles of the quantum circuit.
As one can see in Fig. 5, the agent successfully manages to reach the exact energy within chemical accuracy, despite having a lower bound below the exact value. Moreover, it can be seen that the initial threshold is well above the error that the agent reaches, which also removes the requirement of human input to set the threshold schedule. Similar experiments were performed on bond distances 1.2Å and 3.4Å with the same results.

heading: 6 Discussion

text:
The molecular electronic structure problem is a promising near-term application for quantum computers. The performance of a chosen variational ansatz depends on the structure and depth of its corresponding circuit. Near-term quantum devices pose restrictions on the depth of the VQE circuit. Thus, VQE structure optimization for near-term quantum computers is a multi-objective optimization problem that requires maximizing the expressivity and reducing the depth of the corresponding
circuits. Reinforcement learning by design aims at maximizing the discounted sum of rewards, and as a consequence, this will naturally lead to finding shorter better-performing solutions. This property of RL is one of the main reasons we selected this method.
In this work, we present a deep reinforcement learning architecture with the feedback-driven curriculum learning to optimize the structure of VQE circuits. The goal of this approach is to design circuits that estimate the ground state energy of molecules within chemical accuracy while keeping the circuit depth as low as possible. In our approach, instead of confronting the RL agent with the full-scale problem from the beginning, the agent first starts training on a simpler instance and autonomously adjusts the task complexity until chemical accuracy is achieved. In particular, we demonstrate that our approach yields the ground state energy of LiH within chemical accuracy for several bond distances. While other VQE approaches also reach chemical accuracy for this benchmark, our approach consistently outperforms the others in terms of circuit depth. Hence, the unique combination of deep RL and feedback-driven curriculum learning for structure learning yields an interesting new approach for solving VQE problems.
We emphasize that whilst we focus specifically on the molecular electronic structure problem for LiH, the reinforcement learning approach presented in this paper can be adapted for optimizing other VQE architectures [38, 7]. The method is also directly compatible with other reinforcement learning algorithms, and the angle optimization algorithms are not restricted to the methods investigated in this paper.
In summary, the methods proposed in this work provide state-of-the-art results in electronic structure problem experiments and lay the foundations for the application of deep reinforcement learning methods to VQE optimization problems. Moreover, as is often the case when new methods are employed, we envision numerous follow-up avenues which will reveal the true capacities of such automated ML methods for VQE-type problems.
Broader Impact
Quantum computers may offer significant improvements in chemistry, with applications in drug and material design that could have a widespread positive impact on society (e.g. in the discovery of novel effective pharmaceuticals).
Our work presents novel approaches for enhancing VQE-based methods targeting quantum chemistry problems and thus contributes to this objective. In particular, this research focuses on the use of reinforcement learning to automatically program existing quantum devices. Whilst our work mainly focuses on finding the LiH molecule ground state energy, the benefits of such a technique extend to research questions that can be reformulated as a VQE optimization problem.
We foresee no negative impact stemming from our research, no significant consequences from system failures, nor do we believe our methods leverage any bias in any data.
From the energy consumption perspective, we estimate that the single experiment takes from 12 to 48 hours of computation time using a single CPU. We did not perform any experiments on a QPU machine.
Acknowledgments and Disclosure of Funding
This manuscript builds on the results presented in the NeurIPS workshop paper [39]. MO acknowledge the support of the Foundation for Polish Science (FNP) under grant number POIR.04.04.0000-17C1/18-00. LMT acknowledges the support from the Austrian Science Fund (FWF) through the projects DK-ALM:W1259-N27 and SFB BeyondC F7102. This work was also supported by the Dutch Research Council(NWO/OCW), as part of the Quantum Software Consortium programme (project number 024.003.037). VD and ES acknowledges the support of SURFsara through the QC4QC project. This research was partially funded by the Grant of Priority Research Domain at Warsaw University of Technology - Artificial Intelligence and Robotics. The authors also wanted to thank Arthur G. Rattew for helpful discussions.

title: Reinforcement learning for optimization of variational quantum circuit architectures