# Optimised Multithreaded CV-QKD Reconciliation for Global Quantum Networks

Xiaoyu Ai and Robert Malaney

School of Electrical Engineering & Telecommunications,
University of New South Wales, Sydney, NSW 2052, Australia.

###### Abstract

Designing a practical Continuous Variable (CV) Quantum Key Distribution (QKD)
system requires an estimation of the quantum channel characteristics and the
extraction of secure key bits based on a large number of distributed quantum
signals. Meeting this requirement in short timescales is difficult. On
standard processors, it can take several hours to reconcile the required
number of quantum signals. This problem is exacerbated in the context of Low
Earth Orbit (LEO) satellite CV-QKD, in which the satellite flyover time is
constrained to be less than a few minutes. A potential solution to this
problem is massive parallelisation of the classical reconciliation process in
which a large-code block is subdivided into many shorter blocks for individual
decoding. However, the penalty of this procedure on the important final
secured key rate is non-trivial to determine and hitherto has not been
formally analysed. Ideally, a determination of the optimal reduced block size,
maximising the final key rate, would be forthcoming in such an analysis. In
this work, we fill this important knowledge gap via detailed analyses and
experimental verification of a CV-QKD sliced reconciliation protocol that uses
large block-length low-density parity-check decoders. Our new solution results
in a significant increase in the final key rate relative to non-optimised
reconciliation. In addition, it allows for the acquisition of quantum secured
messages between terrestrial stations and LEO satellites within a flyover
timescale even using off-the-shelf processors. Our work points the way to
optimised global quantum networks secured via fundamental physics.

##  I Introduction

Continuous Variable (CV) Quantum Key Distribution (QKD) has been intensively
studied and significant breakthroughs have been achieved in both theory and
experiment (see [1] for review). Compared to Discrete Variable (DV) QKD [2, 3,
4, 5], CV-QKD can be implemented with well-developed technologies (e.g.,
homodyne detectors) in commercial fibre-optic networks[6, 7] and free-space
optical communications[8, 9], providing it a potential advantage in practical
deployments[10, 11, 12, 13, 14].

Considering the finite-key security of CV-QKD and DV-QKD, there are three
critical parameters. These are, $N_{o}$, the number of original quantum
signals sent by the transmitter (Alice) that are collected by the receiver
(Bob); $N_{e}$, the number of quantum signals from which the protocol
parameters are estimated;111More precisely, in a CV-QKD protocol, Alice and
Bob randomly select a $N_{e}$-signal subset from the $N_{o}$ signals to
estimate the parameters. and, $\epsilon$, the probability that a QKD protocol
fails to generate secret keys[15, 16]. To satisfy an upper limit on the
failure probability of parameter estimation, Alice and Bob set $N_{e}$ to a
large value, which in turn implies a larger $N_{o}$.

Despite the advantages in deployment, CV-QKD systems tend to demand a larger
$N_{o}$ to reach the same $\epsilon$ relative to DV-QKD protocols. For
example, to achieve a final key rate of $0.1$ bits per pulse with
$\epsilon=10^{-9}$, a CV-QKD protocol studied in [17] required $N_{o}\approx
10^{9}$ signals. However, to achieve the same final key rate with
$\epsilon=10^{-14}$, the DV-QKD protocol in [18] required $N_{o}\approx
10^{4}$ signals. This higher number of required signals in CV-QKD can render
the classical post-processing (i.e. key reconciliation and privacy
amplification222In this work, we focus on the key reconciliation step because
it is the more time-consuming part in the post-processing steps while the
privacy amplification involving only bit-wise operations can be easily
implemented faster than the reconciliation [19].) slow - possibly failing to
meet target timescales for reconciliation.

The end-users of a CV-QKD system expect the system to deliver two identical
and secure keys under a limited time interval. For example, for satellite-
based deployments, we would hope that the reconciliation is completed while
maintaining a line-of-sight connection with the ground station. For a CV-QKD-
enabled satellite with orbital parameters similar to _Micius_ [20], this would
mean the reconciliation should be completed in less than a few minutes. For
the protocol we use in this work (see later), and for $\epsilon=10^{-9}$,
this, in turn, would require the data rate of reconciliation to be at least
$3.6\times 10^{6}$ bits per second. For real-time reconciliation (say in sub-
second timescales), two orders of magnitude increases in the reconciliation
rates would be required. Demands for smaller $\epsilon$ will exacerbate the
issue. Ideally, the rate of reconciliation should always be faster than the
rate of quantum signalling.

This all raises the question as to whether current CV-QKD reconciliation
schemes are optimised for the highest possible key rates in bits per second.
As we show here, this is not the case. Further optimisation is possible on all
current schemes.

To understand the issue better, we define reconciliation in the context of CV-
QKD as a two-step scheme where the inputs to the reconciliation are non-
identical $N=2N_{o}-2N_{e}$ quadrature values333 $N_{o}$ and $N_{e}$ are
multiplied by 2 since Alice and Bob utilise both quadratures from heterodyne
detection - the detection process we assume in this work. held by Alice and
Bob (after parameter estimation), and the output is an identical bit string
held by Alice and Bob [21, 22, 23]. Assuming a reverse reconciliation scheme,
Bob first converts the quadrature values encoded by Alice in each signal to
$m$ bits. Alice, after converting each of her encoded real numbers also to $m$
bits, then initiates some discrepancy-correction algorithms based on pre-
defined error-correction codes to ensure her $mN$ bits are identical to Bob’s.
In this work, we will adopt Low-Density Parity-Check (LDPC) codes for the
error correction.

However, as alluded to above, reconciling $mN$ bits within a limited time
frame can be challenging. State-of-the-art LDPC-based reconciliation schemes
for CV-QKD systems involve parallelised computation on a Graphics Processing
Unit (GPU) [24, 13] or Field-Programmable Gate Arrays (FPGAs)[25, 26].
Reconciliation schemes implemented on FPGAs offer more programmable
flexibility, but sometimes at the cost of reduced memory access relative to
GPUs. For our purposes, both hardware architectures are useful - both offer
massive parallelisation opportunities. These parallelisation solutions
generally take the following two-step approach: 1) The $mN$ bits are organised
as $m$ $N$-bit blocks to be reconciled. Each $N$-bit block is divided into
multiple shorter blocks of size, say, $N_{R}$. This is usually just set to a
block size that can be processed within some timescale. 2) Then the $m$
$N_{R}$-bit blocks are reconciled in parallel (via independent processors)
using optimally-designed LDPC decoders. However, what is missing in this
approach is a proper optimisation analysis as to what the optimal value of
$N_{R}$ is. As we show below, simply reducing $N_{R}$ at the cost of
additional processing units is not an optimal solution. It transpires that in
QKD the “penalty” cost of reducing the code rate (implicit in the use of small
block lengths) significantly influences the bit per second final key rate.

A more sophisticated analysis is required to determine the optimal reduced
block length. Such an analysis is the key contribution of this work. Although
we will adopt a specific CV-QKD protocol for our analysis, the key steps of
our scheme will apply to any CV-QKD protocol. Our reconciliation scheme will
deliver the highest reconciliation rate for a given processor speed - thus
allowing for the optimal solution to CV-QKD reconciliation.

##  II System Overview

Although, as just stated, our analysis will apply to most CV-QKD protocols,
for detailed quantitative discussion we will consider only one specific CV-QKD
protocol - the “no-switching” protocol[27, 28, 29] based on heterodyne
detection. In this protocol, the quantum signal is encoded using Gaussian-
modulated coherent states[27]. The main advantage of the no-switching protocol
is that Alice and Bob can utlise all measurement results [28] (in most other
protocols some results are discarded due to a random quadrature selection). We
also adopt a Slice Reconciliation (SR) variant named Multi-Stage Hard
Decoding444The slice reconciliation can be implemented with 2 other variants:
Bit Interleaved Coded Modulation (BICM) [30] and Multi-Level Coding/Multi-
Stage Decoding (MLC/MSD) [31, 32]. We note that the MLC/MSD takes advantage of
the dependence between slices to select the optimal LDPC code rates [30, 32].
However, as a special case of MLC/MSD, MSHD assumes that the slices are
independent [33, 34, 30]. Using MSHD leads to a tractable analysis at the
expense of sub-optimal selection of LDPC code rates, but such expense is
negligible if Gray Labelling [35] is adopted and the number of slices is at
least 5 [34, 30], as is the case in this work. (MSHD) [33, 34, 30] for the
classical reconciliation step, where the number of bits derived from each
measurement outcome is $m$. We refer to this variant simply as SR in the
following.

It is worth noting that the optimisation analysis to follow is to some extent
independent of the details of the reconciliation scheme. However, SR[30, 36]
can be compared with the other well-known reconciliation scheme for CV-QKD -
multi-dimensional reconciliation[37]. It is known that SR achieves higher
reconciliation efficiency when the Signal-to-Noise Ratio (SNR) is greater than
1[36]. At low SNR the opposite is true. For focus, here we adopt SR (as
multistage hard decoding[36]) since in many satellite scenarios post-selection
is used to filter out the low SNR quantum signals [1]. Our adopted scheme will
be more useful in such scenarios.

Figure 1: Diagram of the reconciliation. 1) Alice prepares and sends Gaussian-
modulated coherent states to Bob during the signal transmission. 2) Bob
performs heterodyne detection to obtain quadrature values. Blue diamonds at
Alice’s side represent Alice’s quadrature values. Diamonds filled with tinted
or shaded blue at Bob’s side show that his quadrature values deviate from what
was prepared by Alice after transmission. 3) Alice and Bob select and exchange
a random subset of the quadrature values (diamonds with red outlines) to
perform parameter estimation. 4) Alice and Bob perform reverse reconciliation
based on SR to convert their quadrature values into two bit strings and
reconcile them. 5) Alice and Bob perform privacy amplification to obtain two
identical but shorter key strings about which Eve has effectively no
knowledge.

We now briefly describe the steps of the protocol, a diagram of which shown in
Fig. 1. In the following, we assume the quantum signalling rate is much larger
than the reconciliation rate.

  * •

Step 1: Signal Preparation. Alice selects a fixed modulation variance $V_{A}$.
For each quantum signal to be transmitted to Bob, Alice randomly selects a
number from a Gaussian distribution, $N(0,V_{A})$, and then prepares a signal
by displacing one of the quadrature components of a vacuum state by this
random number. The process is repeated on the signal for the other quadrature.
The signal is then transmitted to Bob.

  * •

Step 2: Heterodyne Detection. Bob performs heterodyne detection to obtain the
two quadrature values (real numbers) for each received signal. Bob compares
each measured quantum signal with a given cut-off threshold and informs Alice
to discard her corresponding quantum signal if his measured quantum signal is
lower than the threshold555The Gaussian post-selection technique at Bob’s side
effectively improves the channel conditions between Alice and Bob[38] so that
SR is preferred for reconciliation (rather than multidimensional
reconciliation).. A quantum signal that is lost in transit registers a null
signal at Bob. Neglecting null signals, Bob holds $2N_{o}$ quadrature values
at the end of this process.

  * •

Step 3: Parameter Estimation. Bob randomly selects a subset $2N_{e}$ from the
$2N_{o}$ quadrature values and sends this _estimation subset_ , along with the
corresponding time information, to Alice via classical communications (we
adopt $N_{e}=\frac{1}{2}N_{o}$, unless otherwise stated). Alice uses the
timing information to best pair the signals in this subset (and therefore the
corresponding quadrature values) sent by her and then estimates the covariance
matrix between the shared states. Based on the estimated covariance matrix,
Alice determines the channel transmissivity, $T$, excess noise, $\xi$, Bob’s
SNR, $\gamma$, the Holevo Information, $\chi_{BE}$, between Bob and the
eavesdropper (Eve), and the mutual information between Alice and Bob,
$I_{AB}$. Finally, for a given target reconciliation efficiency $\beta$, Alice
compares $\chi_{BE}$ with $\beta I_{AB}$. Alice aborts the protocol if
$\chi_{BE}\geq\beta I_{AB}$. Otherwise, Alice informs Bob of the estimation
results, i.e. $T$, $\xi$, $\gamma$, $\chi_{BE}$ and $I_{AB}$.

  * •

Step 4: Bit Error Estimation for SR. Using Gray Labelling, Alice and Bob
represent each of the quadrature values embedded in each signal with $m$ bits.
Then, for quadrature values selected in the estimation subset, Alice forms a
$N_{e}$-by-$m$ bit matrix and Bob does the same. Next, Alice and Bob exchange
their matrices and compare the $j^{th}$ column of the two matrices to estimate
the Bit Error Ratio666At this step, sources of bit errors include the channel
transmission, heterodyne detection, and quantisation. (BER),
$p_{j},j\in\\{0,1,\cdots,m-1\\}$, for all the digits in the $j^{th}$ column.
The estimated $p_{j}$ will be used in SR. Finally, Alice and Bob discard all
the quadrature values in the estimation subset. At the end of this step, Alice
and Bob each hold a $mN$-bit string.

  * •

Step 5: Reverse Reconciliation. For each column, Alice and Bob agree on an
LDPC code with block length $N_{R}$ that is closest to the capacity determined
by $p_{j}$. Bob forms a new $N_{R}$-bit string (referred as a “slice” in SR)
by selecting the $j^{th}$ digit (bit) of each of the $N_{R}$ quadrature
values, encodes the new bit string (the slice) into syndrome bits, and sends
those bits to Alice (see III.B for details). Alice then initiates SR to obtain
her best estimate of Bob’s string. Alice repeats this process until all her
$mN$ bits are reconciled. Finally, Alice and Bob obtain two hashed strings by
applying the same hash function to their reconciled strings and exchange the
hash results to check whether SR is successful. If successful, Alice holds a
$mN$-bit string identical to Bob’s $mN$-bit string. Otherwise, they abort the
protocol and restart from Step 1.

  * •

Step 6: Privacy Amplification. Based on Eq. 19, Alice and Bob compute the
length of the secret key that can be extracted and then apply a 2-universal
hashing function on their reconciled string to obtain two identical and
shorter secret key strings about which Eve has effectively no knowledge.

##  III Overcoming the Limitations of Key Reconciliation

###  III-A GPU-based SR

The process of SR is to reconcile $mN$ bits. One can naively use $m$ LDPC
matrices with $N_{R}=N$ for each matrix. However, due to practical hardware
limitations, the process is better implemented by dividing $N$ into $N_{d}$
blocks of some smaller $N_{R}$ so that the same LDPC decoders can reconcile
these blocks in parallel. This process resembles the idea of Single Program
Multiple Data (see [39, 40] for more details). As illustrated in Fig. 2, we
implement SR by creating $N_{d}$ LDPC decoders loaded with the same LDPC
matrix on $N_{d}$ GPU threads and let these decoders reconcile $N_{d}$ blocks
in parallel. This helps to reduce the SR timescale and assists in meeting the
time constraints, such as those posed in satellite-based scenarios. Section
V-A will demonstrate in detail the advantage of using such parallelisation.

Figure 2: Diagram of GPU-based SR adopted in this work. $N$ quadratures values
are divided into multiple blocks of length $N_{R}$. Each block is loaded to
one thread that is dedicated to performing SR for this block. The reconciled
bits obtained from each thread are collected and ready for privacy
amplification. The floor operator is shown as $[\cdot]$.

###  III-B The Penalty of Using Finite-Length LDPC Codes

An illustration of the SR scheme is shown in Fig. 3. The generic steps are:
_1)_ for the $i^{th}$ quadrature value, $y^{i},i=0,1,\cdots,N_{R}-1$, Bob
applies a constant-step quantisation function, $M(\cdot)$, to convert $y^{i}$
to an $m$-bit string777We assume the least significant bit is $l_{0}^{i}$.
denoted as $\\{l_{0}^{i},l_{1}^{i},\cdots,l_{m-1}^{i}\\}$, where
$l_{j}^{i},j=0,\cdots,m-1$ is the binary bit for the $j^{th}$ digit of the
$i^{th}$ quadrature value. _2)_. We define that the $j^{th}$ slice,
$\mathbf{S_{j}}$, is a bit string with length $N_{R}$ created by Bob:
$\mathbf{S_{j}}=\\{l_{j}^{0},l_{j}^{1},\cdots,l_{j}^{N_{R}-1}\\}$. For
$\mathbf{S_{j}}$, Bob applies an LDPC matrix, $H_{j}$ based on $p_{j}$
obtained in parameter estimation to obtain the corresponding syndrome bits.
_3)_ Bob sends Alice the syndrome bits of $\mathbf{S_{j}}$ and $H_{j}$ via
classical communications. _4)_ Alice uses her quadrature values as side
information and what was transmitted by Bob as the inputs of the LDPC decoder.
Alice takes the soft decoding output (the log-likelihood ratio when the
decoding finishes) of $\mathbf{S_{j-1}}$ as the input to accelerate the
reconciliation of $\mathbf{S_{j}}$ (except for $\mathbf{S_{0}}$)888The
rationale behind this is that the soft decoding output of $\mathbf{S_{j-1}}$
provides a priori information on the reliability of each bit in
$\mathbf{S_{j}}$ [30].[30, 41]. _5)_ Alice obtains her estimated version of
$\mathbf{S_{j}}$. Then, Alice and Bob move on to $\mathbf{S_{j+1}}$. _6)_
Alice and Bob repeat Step 1 to 5 until all $N$ values are reconciled. We note
that Alice and Bob use $m$ LDPC matrices to reconcile $m$ slices in a block -
but the same $m$ LDPC matrices are used for reconciling all $N_{d}$ blocks
since the quantisation errors are the same for a given $m$[42].

Figure 3: Diagram of SR. The red dashed arrows show the soft decoding output
feeds from $\mathbf{S_{j-1}}$ to $\mathbf{S_{j}}$. The red dashed rectangles
are graphical examples of a slice.

In SR, Bob needs to transmit syndrome bits to Alice based on the selected LDPC
matrix with the code rate, $R_{j}$, for $\mathbf{S_{j}}$ via classical
communications. For a given channel condition, selecting $R_{j}$ closest to
the capacity is the common approach to minimise the number of bits disclosed
to the eavesdropper while Alice can still reconstruct Bob’s quantised bits
without error[36]. Specifically, for a given $T$, we can obtain the SNR,
$\gamma$, as [42]

$\gamma=\frac{\frac{1}{2}V_{A}T}{1+\frac{1}{2}\xi}\,,$ (1)

where $V_{A}$ is the modulation variance at Alice side, $\xi=\xi_{ch}+\xi_{d}$
is the total noise power, $\xi_{ch}$ is the channel excess noise, and
$\xi_{d}$ is the detector noise. Finally, the reconciliation efficiency
$\beta\in[0,1]$ for the SR is obtained via [31]

$\beta=\frac{\Pi(M(Y))-m+\sum_{j=0}^{m-1}R_{j}}{I_{AB}}\,,$ (2)

where $Y$ is a vector of Bob’s quadrature values of length $N_{R}$, $M(Y)$ is
a $mN$-bit string obtained by applying the quantisation function $M(\cdot)$ to
each quadrature value in $Y$, and $\Pi(M(Y))$ is the entropy function of
$M(Y)$. Increasing $m$ to values that render the quantisation error negligible
is always possible, but this would require the individual LDPC codes for every
$j^{th}$ slice to be near perfect (capacity-achieving) otherwise the
efficiency $\beta$ will be low; $m=5$ is found to be a good pragmatic
compromise, and is adopted here. Given five slices a constant quantisation
size of the real line across $2^{5}$ bins centered on zero is chosen. This
size, which is dependent on the adopted $\gamma$, optimises $\beta$ (see[31]
for further discussion).

The LDPC code rates, $R_{j}$, in Eq. 2 are the actual rates of the specific
codes used for each slice (of length $N_{R}$). Normally, in practice, $N_{R}$
is simply set to some value that allows target time-frames to be met, given
that the decoding time is an increasing function of the block length[24]. We
use $R_{j}$ to obtain our experimental key rate in Eq. 32. A more nuanced
value of that $N_{R}$ that optimises secure key rates is now analysed.

To make progress in our task, we utilise a previous analysis of channel coding
in the finite block-length[43] regime as a means to further investigate the
effective channel capacity, $C_{Finite}$ for a given block length $N_{R}$ and
$\gamma$. For a finite message set $\mathcal{M}$, $C_{Finite}$ is the ratio of
the maximum size of $\mathcal{M}$ that can be transmitted via $N_{R}$ channel
uses with a decoding error probability less than $\epsilon_{EC}$.
Specifically, for an Additive White Gaussian Noise Channel (AWGNC),
$C_{Finite}$ is given by999This approximation is accurate if the code achieves
more than $80\%$ of the capacity[43].  [43]

$C_{Finite}\approx
C(\gamma)-\frac{\sqrt{N_{R}A}Q^{-1}(\epsilon_{EC})+\frac{1}{2}\log
N_{R}}{N_{R}}\,,$ (3)

where $C(\gamma)=\frac{1}{2}\log(1+\gamma)$ is the Shannon Capacity for the
given $\gamma$, $Q^{-1}(s)$ is the inverse of the Q-function

$Q(z)=\frac{1}{\sqrt{2\pi}}\int_{z}^{\infty}e^{-\frac{t^{2}}{2}}dt\,,$ (4)

and $A$ is given by

$A=\frac{\gamma}{2}\frac{\gamma+2}{(\gamma+1)^{2}}(\log\epsilon_{EC})^{2}\,.$
(5)

Function $A$ is termed the “channel dispersion” since it represents the
reduction of the code rate from the channel capacity due to a tolerated
decoding error probability. It is the “price to pay” for using a code with
finite block length, for a given $\gamma$.

Note, $C_{Finite}$ is the upper bound of $\sum_{j=0}^{m-1}R_{j}$ for a given
$\epsilon_{EC}$ and $N_{R}$. To simplify the determination of the code rate in
the finite-length regime, we determine $C_{Finite}$ instead of each $R_{j}$
for the purpose of analysis. Using Eq. 3 we introduce $\beta_{Finite}$ as an
analytical reconciliation efficiency in the finite LDPC block length regime
(neglecting the information loss due to the quantisation process). This is
given by

$\beta_{Finite}=\frac{C_{Finite}}{I_{AB}}\approx\frac{{I_{AB}}-\frac{\sqrt{N_{R}A}Q^{-1}(\epsilon_{EC})+\frac{1}{2}\log
N_{R}}{N_{R}}}{I_{AB}}\,.$ (6)

Eq. 6 explicitly illustrates how LDPC codes with long block lengths generally
reduce the information disclosed to Eve during reconciliation.

We demonstrate the connection between $\beta_{Finite}$ and $\beta$. Firstly,
we rewrite Eq. 2 as

$\beta=\frac{\Pi(M(Y))-R_{s}}{I_{AB}}\,,$ (7)

where $R_{s}=\sum_{j=0}^{m-1}(1-R_{j})=m-\sum_{j=0}^{m-1}R_{j}$ is the ratio
of syndrome bits sent by Bob to the total number of bits in $m$ slices.
$R_{s}$ is the side-information that Alice uses to reconcile her $m$
slices[32]. It is known that $R_{s}$ satisfies the SlepianWolf Bound [44]

$R_{s}\geq\Pi(M(Y)|X)\,,$ (8)

where $X$ is a vector of Alice’s quadrature values of length $N_{R}$. Applying
Eq. 8 to Eq. 7, we have

$\displaystyle\frac{\Pi(M(Y))-R_{s}}{I_{AB}}$ $\displaystyle\geq$ (9)
$\displaystyle\frac{\Pi(M(Y))-\Pi(M(Y)|X)}{I_{AB}}=\frac{I(M(Y);X)}{I_{AB}}\,,$

where $I(M(Y);X)$ is the total mutual information (after quantisation) between
Alice and Bob. Recalling that $C_{Finite}$ is the upperbound of the mutual
information between Alice and Bob for an LDPC block length, we have the
following

$1\geq\beta\geq\frac{I(M(Y);X)}{I_{AB}}\geq\frac{C_{Finite}}{I_{AB}}=\beta_{Finite}\geq
0\,.$ (10)

###  III-C Analysing the Computational Complexity of SR

An LDPC matrix with block length $N_{R}$ can be defined by the symbol and
check node degree distribution polynomials,
$\lambda(x)=\sum_{a=2}^{\Lambda}\lambda_{a}x^{a-1}$ and
$\rho(x)=\sum_{b=2}^{P}\rho_{b}x^{b-1}$. Here, $\Lambda$ and $P$ are the
highest degrees in $\lambda(x)$ and $\rho(x)$, respectively. We denote the
total number of non-zero entries in an LDPC matrix as $G$, and adopt the well-
known Belief Propagation (BP) decoder[45] for error correction. We define the
total number of arithmetic operations of SR as $\sum_{j=0}^{m-1}E_{j}D_{j}$,
where, for each $\mathbf{S_{j}}$, $E_{j}$ is the number of arithmetic
operations executed within a decoding iteration,101010In a BP decoder, a
decoding iteration is one pass through the decoding algorithm. and $D_{j}$ is
the number of decoding iterations[46]. We note, in our GPU-based SR, $E_{j}$
and $D_{j}$ are different for the $m$ slices of each block since $m$ LDPC
matrices are used to reconcile the $m$ slices. For a channel with constant $T$
and $\xi$, $D_{j}$ is dependent on a target $\epsilon_{EC}$, and on the
polynomials $\lambda(x)$ and $\rho(x)$. Note, for $N_{R}$ larger than
approximately $10^{5}$, $D_{j}$ is independent of $N_{R}$ (a result we will
adopt later). Assuming the Gaussian approximation within the Density Evolution
Algorithm, $D_{j}$ is given by

$D_{j}=\arg\min_{k}\\{q_{k}=f(\gamma,k,\lambda(x),\rho(x))\leq\epsilon_{EC},k\in\mathbb{Z^{*}}\\}\,,$
(11)

where $q_{k}$ is the BER after the $k^{th}$ decoding iteration and given
by[47]

$\displaystyle q_{k}$ $\displaystyle=f(\gamma,k,\lambda(x),\rho(x))$ (12)
$\displaystyle=\sum_{b=2}^{P}\rho_{b}\phi^{-1}\left(1-L^{b-1}\right)\,.$

Here

$L=1-\sum_{a=2}^{\Lambda}\lambda_{a}\phi\left(\log\gamma+\left(a-1\right)q_{k-1}\right)\,,$
(13)

where $q_{0}=0$, and $\phi(v)$ is given by

$\phi(v)=\begin{cases}1-\frac{1}{\sqrt{4\pi
v}}\int_{-\infty}^{+\infty}\tanh\left(\frac{u}{2}\right)e^{-\frac{\left(u-v\right)^{2}}{4v}}du&v>0\\\
1&v=0\,.\end{cases}$ (14)

Finding a closed solution to Eq. 12 is problematic due to the $\phi^{-1}(w)$
term (here $w=\phi(v)$). To make progress, the following approximation for Eq.
14 is used[47]

$\phi(v)\approx\begin{cases}e^{-0.4527v^{0.86}+0.0218}&v>0\\\
1&v=0\,.\end{cases}$ (15)

We then find $\phi^{-1}(w)$ is given by

$\phi^{-1}(w)\approx\begin{cases}\left(\frac{\log{w}-0.0218}{-0.4527}\right)^{1.1628}&0<w<1\\\
0&w=1\,.\end{cases}$ (16)

With this all in place, it is now possible to solve for $D_{j}$ as given by
Eq. 11.

Now we focus on the determination of $E_{j}$. When messages are propagated
from the variable nodes to the check nodes, there are $2G$ multiplications and
$G$ additions[48]. When messages are propagating back to the variable nodes,
there are $4G$ operations required ($2G$ multiplications and $2G$
additions)[48]. Therefore, $E_{j}$ is obtained by[48, 46]

$\displaystyle E_{j}$ $\displaystyle=7G$ (17)
$\displaystyle=7N_{R}(\frac{\sum_{b=2}^{P}\frac{\rho_{b}}{b}}{\sum_{a=2}^{\Lambda}\frac{\lambda_{a}}{a}})(\sum_{b=2}^{P}b\rho_{b})\,.$

The decoding time of the whole reconciliation process, $\Delta t$, is given by

$\Delta t=c_{h}\sum_{j=0}^{m-1}E_{j}D_{j}\,,$ (18)

where $c_{h}$ is a hardware-dependent constant representing the time taken to
complete an arithmetic operation. Clearly, by dividing $N$ values into
multiple blocks with length $N_{R}$ and decoding these blocks simultaneously,
Alice and Bob can reduce the decoding time by a factor of
$N_{d}=\frac{N}{N_{R}}$.

##  IV Final Key Rate

We now present the penalty incurred for the division of $N$ in the finite-key
regime, and then propose an optimisation procedure to find the optimal $N_{R}$
which maximises the final key rate in bits per second.

###  IV-A Analysis of the Final Key Rate

For the protocol considered, in the finite-key regime the final key rate in
bits per pulse, $K$, under the assumption of Gaussian collective attacks is
adopted as [49, 50, 28]111111This key-rate formulation was developed in [49]
with a typographical error corrected in [50]. Eq. 19 is from [28] which
acknowledged the correction and simplified the final key rate formulation (see
footnote 2 of [51] for more details). A general discussion on the use of other
key-rate formulations (e.g. [52, 53]) within our framework is given later.

$K=\frac{N(\beta
I_{AB}-S_{BE}^{\epsilon_{PE}})-\sqrt{N}\Delta_{AEP}-2\log_{2}\frac{1}{2\epsilon_{PA}}}{N_{o}}\,,$
(19)

where $S_{BE}^{\epsilon_{PE}}$ is the upper bound of the estimated $\chi_{BE}$
(note $K$ is an upper bound, which we assume is reached). The determination of
$S_{BE}^{\epsilon_{PE}}$ is carried out and utilised in the key rates derived
here, but this determination is somewhat lengthy. As such, the reader is
referred to the appendix for a full explanation and derivation of this term.
We simply note here that $S_{BE}^{\epsilon_{PE}}$ is dependent on estimates of
the channel parameters and therefore on the value of $N_{e}$, the number of
symbols sacrificed in the estimation. In Eq. 19, $\Delta_{AEP}$ is a penalty
term (derived using the Asymptotic Equipartition Property of a stochastic
source) due to the finite number of bits used in quantisation and privacy
amplification, and is given by

$\displaystyle\Delta_{AEP}=$
$\displaystyle(m+1)^{2}+4(m+1)\sqrt{\log_{2}(\frac{2}{\epsilon^{2}_{s}})}$
(20)
$\displaystyle+2\log_{2}(\frac{2}{\epsilon^{2}\epsilon_{s}})+\frac{4\epsilon_{s}m}{\epsilon\sqrt{N}}\,,$

where $\epsilon=\epsilon_{EC}+2\epsilon_{s}+\epsilon_{PA}+\epsilon_{PE}$ is
the probability that a QKD protocol fails to generate secret keys. Here,
$\epsilon_{s}$ is the smoothing parameter associated with the smooth min-
entropy calculation, $\epsilon_{PA}$ is the failure probability of the privacy
amplification, and $\epsilon_{PE}$ is the probability that the true value of
$\chi_{BE}$ is not within the confidence interval calculated during parameter
estimation. For a given $\epsilon$, one can determine the values of
$\epsilon_{EC}$, $\epsilon_{s}$, $\epsilon_{PA}$, and $\epsilon_{PE}$ by
setting them individually or collectively as part of the maximisation of $K$
(see Eqs. 18 – 21 in [17] for details).

We consider the penalty on the final key rate caused by dividing $N$ into sub-
blocks of length $N_{R}$. Replacing $\beta$ in Eq. 19 with the
$\beta_{Finite}$ of Eq. 6, we obtain the final key rate with the finite LDPC
block length effect fully considered. The new rate is given by

$K_{Finite}=\frac{N(C_{Finite}-S_{BE}^{\epsilon_{PE}})-\sqrt{N}\Delta_{AEP}-2\log_{2}\frac{1}{2\epsilon_{PA}}}{N_{o}}\,.$
(21)

Thus far, we have been analysing the final key rate in bits per pulse.
However, the final key rate in bits per second is more interesting in our
context - the system will not be viable if the reconciliation takes too long
to complete. From this point forward, we use a dashed symbol to distinguish a
final key rate that is given in bits per second. Taking the decoding
complexity into account, and ignoring the time taken to acquire the quantum
signals, we can write the final key rate, $K_{Finite}^{\prime}$, as

$\displaystyle K_{Finite}^{\prime}$
$\displaystyle=\frac{N_{o}K_{Finite}}{\Delta t}$ (22)
$\displaystyle=\frac{N(C_{Finite}-S_{BE}^{\epsilon_{PE}})-\sqrt{N}\Delta_{AEP}-2\log_{2}\frac{1}{2\epsilon_{PA}}}{c_{h}\sum_{j=0}^{m-1}E_{j}D_{j}}\,.$

We observe that $\Delta t$ in Eq. 18 and $C_{Finite}$ in Eq. 3 are increasing
functions of $N_{R}$. We are interested in finding a unique $N_{R}$ so that
$K_{Finite}^{\prime}$ is maximised.

###  IV-B Optimised LDPC Blocklength for CV-QKD Reconciliation

Previously, we have shown that parallelisation reduces the decoding time at
the expense of increased information disclosure to Eve. In this section, we
demonstrate an optimisation process to find the unique $N_{R}$ maximising
$K_{Finite}^{\prime}$.

We consider a scenario where $\epsilon_{EC}$, $\epsilon_{s}$, $\epsilon_{PA}$,
and $\epsilon_{PE}$ are manually set by end users. We can formulate the
optimisation problem for the scenario

$\displaystyle\max_{N_{R}}$ $\displaystyle K_{Finite}^{\prime}$ (23) s.t.
$\displaystyle 10^{5}\leq N_{R}\leq N\,,$

where $K_{Finite}^{\prime}$ is defined in Eq. 22. The lower limit of $10^{5}$
arises from our earlier discussion on ensuring $D_{j}$ is independent of
$N_{R}$ (for smaller values of $N_{R}$ the penalty cost will be prohibitive
and we ignore this range). We notice that $\Delta t$ is a linear function of
$N_{R}$121212Recalling Eq. 18, we note that for a given LDPC code, $E_{j}$ is
only dependent on the degree distribution pairs and $D_{j}$ is only a function
of the degree distribution pairs and $\gamma$. and $S_{BE}^{\epsilon_{PE}}$;
and that $\Delta_{AEP}$ and $\epsilon$ are independent of $N_{R}$. Therefore,
we can rewrite Eq. 23 in the simplified form

$\displaystyle\max_{N_{R}}$
$\displaystyle\frac{NC_{Finite}-B_{1}}{B_{2}N_{R}}$ (24) s.t. $\displaystyle
10^{5}\leq N_{R}\leq N\,,$

where

$\displaystyle B_{1}=$ $\displaystyle
NS_{BE}^{\epsilon_{PE}}+\sqrt{N}\Delta_{AEP}+2\log_{2}\frac{1}{2\epsilon_{PA}}\,\,,$
(25) $\displaystyle B_{2}=$
$\displaystyle\sum_{j=0}^{m-1}7(\frac{\sum_{b=2}^{P}\frac{\rho_{b}}{b}}{\sum_{a=2}^{\Lambda}\frac{\lambda_{a}}{a}})(\sum_{b=2}^{P}b\rho_{b})D_{j}c_{h}\,.$
(26)

To solve this optimisation problem, firstly we show that the second derivative
of $K_{Finite}^{\prime}$ with respect to $N_{R}$ is less than zero for all
$N_{R}$ considered, where

$\displaystyle\frac{d^{2}K_{Finite}^{\prime}}{dN^{2}_{R}}=$
$\displaystyle\frac{-1}{4B_{2}N^{4}_{R}}\left(\left(12N\log
N_{R}-10N\right)\right.$ (27)
$\displaystyle\left.+15\sqrt{A}Q^{-1}(\epsilon_{EC})N\sqrt{N_{R}}\right.$
$\displaystyle\left.-\left(8I_{AB}NN_{R}-8B_{1}N_{R}\right)\right)\,.$

To show that the RHS of Eq. 27 is less than zero for all $N_{R}$ considered,
it is equivalent to show

$\displaystyle 12N\log N_{R}-10N+15\sqrt{A}Q^{-1}(\epsilon_{EC})N\sqrt{N_{R}}$
(28) $\displaystyle>\left(8I_{AB}NN_{R}-8B_{1}N_{R}\right)\,.$

We find that the LHS of inequality 28 is greater than zero for $N>N_{R}>10$,
$\gamma>0$, and $\epsilon_{EC}<\frac{1}{2}$, but the sign of the RHS is
subject to specific CV-QKD parameters. However, through detailed numerical
search we find that the inequality 28 holds for the range of parameters
anticipated for realistic CV-QKD deployments.131313In using this technique it
is important to check that the inequality holds for the chosen parameter range
of interest. This is done for all calculations we show here, but also for a
much wider range not shown. For example, we find for $\epsilon=10^{-9}$,
$N=10^{9}$ and $m=5$, the inequality 28 holds for any combination of the
remaining parameters selected from the ranges $V_{A}\in[1,34]$, $T\in[0,1]$
and $\xi=[0,0.05]$.  For example, if we consider the following CV-QKD
settings141414The values of $\xi_{ch}$ and $\xi_{d}$ in the standard CV-QKD
settings are predicted values after accounting for all noise terms [17]. (in
the following we refer to these as the standard CV-QKD settings); $N=10^{9}$,
$m=5$, $\epsilon_{EC}=2\epsilon_{s}=\epsilon_{PA}=\epsilon_{PE}=2.5\times
10^{-10}$, $V_{A}=5$, $T=0.9$, $\xi_{ch}=0.0186$ and $\xi_{d}=0.0133$, we find
that the LHS of the inequality is greater than $10^{12}$ and the RHS of the
inequality is less than $10^{11}$.

To find the maximised $K_{Finite}^{\prime}$, we first find the value of
$N_{R}$ that satisfies $\frac{dK_{Finite}^{\prime}}{dN_{R}}=0$, where

$\displaystyle\frac{dK_{Finite}^{\prime}}{dN_{R}}$
$\displaystyle=\frac{N_{R}N\frac{dC_{Finite}}{dN_{R}}-\left(NC_{Finite}-B_{1}\right)}{B_{2}N^{2}_{R}}$
(29)
$\displaystyle=-\frac{NI_{AB}}{B_{2}N^{2}_{R}}-\frac{N}{2B_{2}N^{3}_{R}}+\frac{3N\sqrt{A}Q^{-1}(\epsilon_{EC})}{2B_{2}N^{\frac{5}{2}}_{R}}$
$\displaystyle+\frac{N\log
N_{R}}{B_{2}N^{3}_{R}}+\frac{B_{1}}{B_{2}N^{2}_{R}}\,.$

Therefore, our equation to be solved is given by

$-\frac{NI_{AB}}{B_{2}N^{2}_{R}}-\frac{N-2N\log
N_{R}}{2B_{2}N^{3}_{R}}+\frac{3N\sqrt{A}Q^{-1}(\epsilon_{EC})}{2B_{2}N^{\frac{5}{2}}_{R}}+\frac{B_{1}}{B_{2}N^{2}_{R}}=0\,.$
(30)

Eq. 30 can be solved via a numerical root-finding algorithm[54]. If we
consider the standard CV-QKD settings, we obtain a stationary point at
$N_{R}=3.6\times 10^{7}$ bits (the value of $K^{\prime}_{Finite}$ at this
$N_{R}$ is discussed later).

In closing this section we note the following in regard to alternate key-rate
equations. Although we have adopted a specific CV-QKD protocol and specific
key rate equation, different security analyses of our adopted protocol, and
analyses of different CV-QKD protocols, can have a key rate with a similar
form to that shown in Eq. 19 albeit with different bounded rates. When
comparing different key-rate equations it is perhaps useful to only consider
the leading terms. This allows for clearer tractability in determining the
optimal $N_{R}$. For example, if the last term in our Eq. 20 is neglected (a
good approximation for reasonable $N$ values) then the functional dependence
on $N$ of many key-rate equations is identical. In such circumstances, the
same key rate can be mapped to alternate security settings of the different
key-rate equations, and our framework applies directly. For example, using the
key rate equation of [52] we find the same optimal $N_{R}$ albeit with a
normalised key rate of one for the following security settings (described with
the notations in[52]): the number of quantum signal exchanged, $N=10^{9}$, the
number of quantum signals sacrificed for parameter estimation,
$m=\frac{N}{2}$, the probability of successful reconciliation, $p_{ec}=0.95$,
the smoothing parameter, $\epsilon_{s}=3.2\times 10^{-13}$, the hashing
parameter $\epsilon_{h}=4.7\times 10^{-13}$, the probability that the true
value of the square-root transmissivity is less than the value obtained by the
worst-case estimator used in parameter estimation, $\epsilon_{pe}=1.2\times
10^{-13}$, the residue probability that Alice and Bob’s bit strings are
different after passing the error correction, $\epsilon_{cor}=0.8\times
10^{-13}$, the modulation variance, $\sigma^{2}_{x}=7.1$, the size of the
effective alphabet after quantising the continuous quadrature values,
$d=2^{5}=32$, the channel transmissivity, $T=0.81$, the channel noise
$\sigma^{2}_{z}=0.035$, and the quantum duty to pay by the detector,
$\nu_{det}=2$ for heterodyne detection. Key-rate equations with different
functional dependence on $N_{R}$ can still be analysed within the framework
proposed here - albeit via modified optimisation relations. Examples of this
arise in consideration of DV-QKD protocols (albeit for which reconciliation
optimisation is usually less important). We also note that extension of our
adopted CV-QKD key-rate equation, to cover the most general attack, is
possible via the use of the Gaussian de Finetti reduction technique and the
inclusion of an energy test [55]. This leads to a scaling of order $N^{4}$ in
terms of the security cost.

##  V Experimental Results

We conducted an experiment of our GPU-based SR on a NVIDIA GTX 1060 GPU (with
6GB GPU memory). The GPU provides up to 1280 Compute Unified Device
Architecture (CUDA) threads that can be run simultaneously. We determine the
BER after decoding, denoted as $p_{Decode}$ (different from the $p_{j}$
obtained at Step 5 of the protocol). We also measured the decoding time for
$mN$ bits. Below, we determine the experimental final key rate,
$K_{exp}^{\prime}$, and compare it with $K_{Finite}^{\prime}$ to verify the
optimality of $N_{R}$ found in Section IV-B. We note that the experimental
data shown in Figs. 4, 5, and 6 is averaged over 50 runs. We also note, in our
specific GPU the number of threads available was less than the number of
blocks when $N_{R}=10^{5}$. This was numerically compensated for in the
results shown.

In the experiment, we assume that Alice and Bob complete the first four steps
of the protocol described in Section II. Since Alice and Bob’s quadrature
values are the input and output of an AWGNC, we can generate these quadrature
values for SR in the following way. 1) For a given $V_{A}$, $T$, and $\xi$, we
obtain the noise power, $\sigma^{2}_{n}$ of the AWGNC from Eq. 1

$\gamma=\frac{\frac{1}{2}V_{A}T}{1+\frac{1}{2}\xi}=\frac{1}{\frac{1+\frac{1}{2}\xi}{\frac{1}{2}V_{A}T}}=\frac{1}{\sigma^{2}_{n}}\,.$
(31)

2) We generate $N$ random numbers from the distribution $N(0,V_{A})$. These
numbers are regarded as Alice’s quadrature values and denoted as
$\mathbf{x}=\\{x_{0},x_{1},\cdots,x_{N-1}\\}$. 3) We obtain Bob’s quadrature
values $\mathbf{y}$, where the _i_ th component is given by $y_{i}=x_{i}+n$,
and where $n$ is a random real number drawn from $N(0,\sigma^{2}_{n})$.

###  V-A Decoding Error and Time

In Fig. 4, we compare the BER performance of different $N_{R}$ settings for
each $T$ considered151515Recall, we are particularly interested in the
satellite-to-Earth channel. As in other works, we assume losses for this
channel are dominated by diffraction effects, and therefore the transmissivity
can be held constant. We further assume post-selections, using a bright
classical beam sent along with the quantum signals (but different
polarisation), remove any significant transmissivity deviations. As discussed
elsewhere[17], some receiver/transmitter apertures, coupled to detailed phase-
screen simulations of satellite downlink channels, render the constant-
transmissivity assumption reasonable[56]. If the transmissivity is highly
variable the optimal block length, $N_{R}$, can be calculated by an
expectation over the transmissivity density function.. The solid lines
represent the best straight-line fit of the experimental data for each
$N_{R}$. We note that for a given $T$, the LDPC code rates are set to $10\%$
lower than the capacity for that $T$. In Fig. 4, we observe that larger LDPC
codes lead to a lower $p_{Decode}$. This observation is consistent with the
result of the finite-length information theory[43].

In Fig. 5, we determine the measured decoding time for $mN$ bits in the
experiment, $\Delta t_{exp}$, which is normalised to the value at
$N_{R}=10^{9}$ ($\Delta t_{exp}=310$ seconds). The differences of the measured
decoding time at each $N_{R}$ reflect additional decoding iterations. Our
results confirm the reduction of $\Delta t_{exp}$ when a smaller $N_{R}$ is
used. We note that it is difficult to quantify the exact relation between
$\Delta t_{exp}$ and $N_{R}$ since $\Delta t_{exp}$ includes the elapsed time
taken by SR’s arithmetic operations and the elapsed time for the overhead;
mostly due to memory access operations and synchronisation (we estimate this
shortly). However, our experiment generally confirms the advantage of
parallelisation in decoding time.

Figure 4: $p_{Decode}$ after decoding for different $T$ and $N_{R}$. For each
colour, the crosses are the experimental data obtained. Figure 5: Normalised
decoding time vs. $T$ for different $N_{R}$. For each colour, the crosses are
$\Delta t_{exp}$ obtained in our experiment. For each $T$, the data presented
is the ratio of $\Delta t_{exp}$ for each $N_{R}$ to the decoding time for
$N_{R}=10^{9}$. The advantage offered by GPU parallel processing is seen to
improve decoding times by $\sim 30\%$ for sub-blocks of length $10^{6}$.

###  V-B The Optimal $N_{R}$

Previously, we have analytically found the optimal $N_{R}$ which maximises
$K_{Finite}^{\prime}$. Now we wish to check the compatibility of this $N_{R}$
with the value that maximises $K_{exp}^{\prime}$ based on realistic LDPC codes
and the specific GPU used in our experiment.

For this experiment, we pre-built a database to store LDPC codes with their
code rates ranging from $0.01$ to $0.8$ and their block lengths ranging from
$10^{6}$ to $10^{9}$. For code rates less than $0.1$, Multi-Edge-Type LDPC
codes (degree distributions outlined in [22]) were used. These achieve a lower
$p_{Decode}$ compared to irregular LDPC codes with the same code rate. For
code rates greater than or equal to $0.1$, we adopted the irregular LDPC codes
(degree distributions outlined in[57]). At such code rates, these latter codes
have the same $p_{Decode}$ performance as the Multi-Edge-Type counterparts,
but allow for faster code construction.

We use the following process to obtain $K_{exp}^{\prime}$ for each $N_{R}$
considered. 1) For each $\mathbf{S_{j}}$, we select an LDPC code whose code
rate is closest to the capacity determined by $p_{j}$ from the pre-built
database. 2) We use the selected code to test whether the probability of an
error correction failure of that code is less than $\epsilon_{EC}$. 3) If the
test fails, we decrease $R_{j}$ by $\Delta R=0.05$, select another LDPC code
from the database and go back to Step 2). Otherwise, we mark the selected code
as “good” and then go back to Step 1) for the next slice. The process
terminates when all slices have been successfully decoded. We then obtain
$K_{exp}^{\prime}$ using

$K_{exp}^{\prime}=\frac{N(\sum_{j=0}^{m-1}R_{j}-S_{BE}^{\epsilon_{PE}})-\sqrt{N}\Delta_{AEP}-2\log_{2}\frac{1}{2\epsilon_{PA}}}{\Delta
t_{exp}}\,.$ (32)

We note that the overhead mentioned earlier is one of the sources causing the
discrepancy between $K_{exp}^{\prime}$ and $K_{Finite}^{\prime}$. To
compensate the additional decoding time due to the overhead for all $N_{R}$
considered, we adopt a numerical search for a compensated $\Delta t_{exp}$ so
that $|K_{exp}^{\prime}-K_{Finite}^{\prime}|^{2}$ is minimised. Our result
shows that $K_{exp}^{\prime}$ after compensation is approximately $10\%$
higher than the uncompensated $K_{exp}^{\prime}$. In Fig. 6, we plot
$K_{Finite}^{\prime}$ and $K_{exp}^{\prime}$ (compensated and uncompensated)
with respect to $N_{R}$ based on Eqs. 22 and 32, respectively.

Figure 6: Final Key Rate vs. LDPC Block Length. Here, we adopt the standard
CV-QKD settings for the red and the blue curves. For the green curve, we adopt
the following settings: $N=10^{10}$, $m=5$,
$\epsilon_{EC}=2\epsilon_{s}=\epsilon_{PA}=\epsilon_{PE}=2.5\times 10^{-7}$,
$V_{A}=4$, $T=0.92$, $\xi_{ch}=0.0180$ and $\xi_{d}=0.0128$. We also set
$c_{h}=3.2\times 10^{-9}$ seconds for the red and green curves. All the curves
are normalised to the maximum of the red curve, i.e.
$K_{Finite}^{\prime}=4.3\times 10^{5}$ bits per second at $N_{R}=3.6\times
10^{7}$.

The optimal $N_{R}=3.6\times 10^{7}$ and $5\times 10^{6}$ are found for
$K_{Finite}^{\prime}$ and $K_{exp}^{\prime}$, respectively. Assuming the usual
practical scheme where $N_{R}$ is simply selected randomly, our results for
the standard CV-QKD settings show that using the optimal $N_{R}$ for SR leads
to a maximum gain of $33\%$ on the final key rate. Other CV-QKD settings will
provide different maximum gains. For example, the green curve of Fig. 6
provides for a $66\%$ gain (not shown in the figure are the rates for
$N_{R}>10^{9}$). This point emphasises the need to consider the parameter
settings before determining both the optimal $N_{R}$ and the gain achieved
relative to the standard practice of simply picking some $N_{R}<N$. Note that
in our rate determinations, the normalisation of one in Fig. 6 corresponds to
a key rate $K_{Finite}^{\prime}=4.3\times 10^{5}$ bits per second, based on
our hardware-specific value of $c_{h}=3.2\times 10^{-9}$ seconds.161616We
adopted the following method to determine $c_{h}$. For $m$ LDPC codes with
$N_{R}=10^{6}$ and $T=0.9$, we obtained the total number of arithmetic
operations for those codes. Next, we measured the elapsed time to reconcile a
block of $10^{6}$ quadrature values. We then obtained $c_{h}$ by dividing the
number of arithmetic operations to this measured elapsed time. The
reconciliation rate associated with this same key rate is $3.9\times 10^{6}$
bits per second. Assuming the source rate of the quantum signalling was high
enough (_e.g._ a 100MHz source), this reconciliation rate is higher than that
required for delivery of secured ($\epsilon=10^{-9}$) keys ($N=10^{9}$) within
flyover times (270 seconds) consistent with Micius-type orbits (see the
introduction).

Comparing the two curves in Fig. 6, we find that there is still a small
discrepancy between $K_{Finite}^{\prime}$ and $K_{exp}^{\prime}$ although they
share a similar trend. The reason for such discrepancy is twofold. Firstly,
there remain small trapping sets in the LDPC matrices.171717These trapping
sets are the primary reason that additional decoding iterations are consumed
for only a marginal decrease of the decoding error, i.e. the error floor
effect[58]. Although not part of our analysis (but included in the
uncompensated curve of Fig. 6), we attempted to remove these trapping sets in
our codes by using the algorithm of [58] so that fewer iterations will be used
[59]. This reduced the number of decoding iterations by approximately $15\%$
for $N_{R}=10^{6}$ but did not remove the trapping sets completely. The
remnant trapping sets inside the LDPC matrices lead to a larger number of
decoding iterations than predicted by $D_{j}$. Determined by the Density
Evolution Algorithm, $D_{j}$ is a lower bound due to the assumption of cycle-
free matrices and infinitely long block length[60]. Secondly, we note that
selecting $R_{j}$ so that $\sum_{j=0}^{m-1}R_{j}$ achieves $C_{Finite}$ may
lead to a $p_{Decode}$ higher than the given $\epsilon_{EC}$. In our
experiment (and included in the shown results), we find that the
$K_{exp}^{\prime}$ is $9\%$ lower than the $K_{Finite}^{\prime}$ predicted by
Eq. 22 due to the gap between $\sum_{j=0}^{m-1}R_{j}$ and $C_{Finite}$.

###  V-C Final-key Effect for a Given $N_{o}$

In the satellite-based scenario, Alice and Bob starts the protocol with only
$N_{o}$ quantum signals because the satellite is only visible to the ground
station for a limited time frame. In this section, we revisit the analysis of
the final key rate in the finite-key regime and conduct a numerical search to
show how the final key rate $K$ is affected by $N_{e}$, for a given $N_{o}$
and $\epsilon$.

Figure 7: $K$ (in bits per pulse) vs. $N_{e}$ when $N_{o}=10^{9}$ (blue) and
$N_{o}=10^{10}$ (red). Here, we adopt the standard CV-QKD settings except that
$N=2\left(N_{o}-N_{e}\right)$ varies for different $N_{e}$.

In Fig. 7, we observe that $K$ is cut off when $N_{e}$ approaches $10^{7}$ and
$10^{9}$ (for $N_{o}=10^{9}$). At $N_{e}=10^{7}$, the parameter confidence
intervals are not consistent with a positive $K$. As $N_{e}$ approaches
$N_{o}$, $K$ decreases rapidly since the number of quantum signals for
reconciliation approaches zero. Similar remarks can also be applied for
$N_{o}=10^{10}$. In Fig. 7, we see that setting $N_{e}=\frac{N_{o}}{2}$ is an
acceptable compromise between accommodating finite-key effects and preserving
enough quantum signals for the post-processing. In the appendix, we
investigate varying $N_{e}$ but where it is always constrained to
$N_{e}=\frac{N_{o}}{2}$.

##  VI Discussion

We close our work with a brief discussion on recent developments in high-rate
CV-QKD reconciliation via the massive parallelisation offered by GPUs and
FPGAs. In [24], a GPU-based LDPC decoder was implemented, achieving a rate of
$9\times 10^{6}$ bits per second. In this implementation all GPU threads were
used to minimise the decoding time of a _single_ LDPC block of $2^{20}$ bits.
In [61] and [62], the reconciliation rates were further increased to $3\times
10^{7}$ and $6\times 10^{7}$ bits per second, respectively, by simultaneously
decoding _multiple_ LDPC blocks of length $10^{6}$ bits on a GPU. To our
knowledge, the highest reconciliation rate obtained thus far is $2\times
10^{8}$ bits per second - an outcome based on an FPGA [25]. All of these works
show promise for the delivery of practical CV-QKD systems in which
reconciliation does not become the bottleneck of the QKD process. However,
none have introduced the type of optimisation we have introduced in this work
and, therefore, all are likely candidates for further improvement in terms of
the choice of the optimal block length. Based on our results we would
anticipate this improvement to be significant for a wide range of CV-QKD
parameter settings. Our work is also different from the above works in the
following (less important) aspects.

1) Reconciliation schemes for satellite-based CV-QKD. High-speed
implementations realised in [61, 62] have used multidimensional reconciliation
[37]. This multidimensional scheme is preferred for low SNR - but not so for
the higher SNRs available via the Gaussian post-selection technique - a
technique likely to be more useful in the satellite context [1].

2) Low probability of reconciliation failures. In CV-QKD, Alice and Bob have
to discard a block of reconciled bits if they detect a reconciliation failure
(coding error) for that block. To compensate for the discarded bits,
additional quantum signals need to be transmitted and reconciled, causing
unwanted delays. Such delays can be problematic for satellite-based systems
since the satellite is not always visible to the ground station. The FPGA-
based reconciliation of [25] may suffer from this problem due to limited
precision of arithmetic operations leading to higher reconciliation failures.
As shown in many GPU-based works (including this work), GPU-based
reconciliation offers less probability of reconciliation failure.

##  VII Conclusion

In this work, we have carried out a full-blown analysis and experimental
implementation of a Slice Reconciliation scheme applied to a specific CV QKD
protocol (with post-selection) under simulated channel conditions anticipated
for satellite-to-Earth channels. We have provided the optimal solution for the
classical reconciliation process for this CV-QKD protocol in the context of
massive parallelisation under the finite key regime. More specifically, we
have identified the optimal block length when a large-code block is to be
subdivided so as to improve the final secure key rate in bits per second.
Although our results were based on a specific CV-QKD protocol and a specific
GPU architecture, the type of analysis we have introduced here will apply in
general terms a large suite of CV-QKD protocols run over any form of
architecture that offers massive parallelisation. Our results, therefore, pave
the way to optimal reconciliation system design for a wide range of practical
CV-QKD systems that operate in the finite key regime. As the demand on the
finite key size grows (better security thresholds), and technology advances
lead to larger quantum signalling rates, the importance of optimised
multithreaded CV-QKD reconciliation will grow.

## References

  * [1] N. Hosseinidehaj, Z. Babar, R. Malaney, S. X. Ng, and L. Hanzo, “Satellite-Based Continuous-Variable Quantum Communications: State-of-the-Art and a Predictive Outlook,” IEEE Communications Surveys & Tutorials, vol. 21, no. 1, 881–919, 2018.
  * [2] C. H. Bennett and G. Brassard, “Quantum Cryptography: Public Key Distribution and Coin Tossing,” in Proceedings of IEEE International Conference on Computers, Systems and Signal Processing,, vol. 175, 8, 1984.
  * [3] H. Weinfurter, “Quantum Communication Experiments with Discrete Variables,” Quantum Information: From Foundations to Quantum Technology Applications, 369–381, 2016.
  * [4] L. Gyöngyösi, L. Bacsardi, and S. Imre, “A Survey on Quantum Key Distribution,” Infocommunications Journal, vol. 11, no. 2, 14–21, 2019\.
  * [5] S. Pirandola, U. L. Andersen, L. Banchi, M. Berta, D. Bunandar, R. Colbeck, D. Englund, T. Gehring, C. Lupo, C. Ottaviani, et al., “Advances in Quantum Cryptography,” Advances in Optics and Photonics, vol. 12, no. 4, 1012–1236, 2020.
  * [6] B. Korzh, C. C. W. Lim, R. Houlmann, N. Gisin, M. J. Li, D. Nolan, B. Sanguinetti, R. Thew, and H. Zbinden, “Provably Secure and Practical Quantum Key Distribution over 307 km of Optical Fibre,” Nature Photonics, vol. 9, no. 3, 163–168, 2015.
  * [7] T. A. Eriksson, T. Hirano, B. J. Puttnam, G. Rademacher, R. S. Luís, M. Fujiwara, R. Namiki, Y. Awaji, M. Takeoka, N. Wada, et al., “Wavelength Division Multiplexing of Continuous Variable Quantum Key Distribution and 18.3 Tbit/s Data Channels,” Communications Physics, vol. 2, no. 1, 1–8, 2019.
  * [8] S.-Y. Shen, M.-W. Dai, X.-T. Zheng, Q.-Y. Sun, G.-C. Guo, and Z.-F. Han, “Free-Space Continuous-Variable Quantum Key Distribution of Unidimensional Gaussian Modulation Using Polarized Coherent States in an Urban Environment,” Physical Review A, vol. 100, 012325, 2019.
  * [9] L. Gyongyosi and S. Imre, “Secret Key Rates of Free-Space Optical Continuous-Variable Quantum Key Distribution,” International Journal of Communication Systems, vol. 32, no. 18, e4152, 2019.
  * [10] P. Jouguet, S. Kunz-Jacques, and A. Leverrier, “Long-Distance Continuous-Variable Quantum Key Distribution with a Gaussian Modulation,” Physical Review A, vol. 84, no. 6, 062317, 2011.
  * [11] P. Jouguet, S. Kunz-Jacques, T. Debuisschert, S. Fossier, E. Diamanti, R. Alléaume, R. Tualle-Brouri, P. Grangier, A. Leverrier, P. Pache, et al., “Field Test of Classical Symmetric Encryption with Continuous Variables Quantum Key Distribution,” Optics Express, vol. 20, no. 13, 14030–14041, 2012.
  * [12] Q. Liao, Y. Guo, D. Huang, P. Huang, and G. Zeng, “Long-Distance Continuous-Variable Quantum Key Distribution Using Non-Gaussian State-Discrimination Detection,” New Journal of Physics, vol. 20, no. 2, 023015, 2018.
  * [13] D. Guo, C. He, T. Guo, Z. Xue, Q. Feng, and J. Mu, “Comprehensive High-Speed Reconciliation for Continuous-Variable Quantum Key Distribution,” Quantum Information Processing, vol. 19, no. 9, 1–19, 2020.
  * [14] Y. Zhang, Z. Chen, S. Pirandola, X. Wang, C. Zhou, B. Chu, Y. Zhao, B. Xu, S. Yu, and H. Guo, “Long-Distance Continuous-Variable Quantum Key Distribution over 202.81 km of Fiber,” Physical Review Letters, vol. 125, no. 1, 010502, 2020.
  * [15] A. Leverrier, F. Grosshans, and P. Grangier, “Finite-Size Analysis of a Continuous-Variable Quantum Key Distribution,” Physical Review A, vol. 81, no. 6, 062343, 2010.
  * [16] F. Furrer, T. Franz, M. Berta, A. Leverrier, V. B. Scholz, M. Tomamichel, and R. F. Werner, “Continuous Variable Quantum Key Distribution: Finite-Key Analysis of Composable Security against Coherent Attacks,” Physical Review Letters, vol. 109, no. 10, 100502, 2012.
  * [17] S. Kish, E. Villaseñor, R. Malaney, K. Mudge, and K. Grant, “Feasibility Assessment for Practical Continuous Variable Quantum Key Distribution over the Satellite-to-Earth Channel,” Quantum Engineering, vol. 2, no. 3, e50, 2020.
  * [18] M. Tomamichel, C. C. W. Lim, N. Gisin, and R. Renner, “Tight Finite-Key Analysis for Quantum Cryptography,” Nature Communications, vol. 3, no. 1, 1–6, 2012.
  * [19] Z. Yuan, A. Plews, R. Takahashi, K. Doi, W. Tam, A. Sharpe, A. Dixon, E. Lavelle, J. Dynes, A. Murakami, et al., “10-Mb/s Quantum Key Distribution,” Journal of Lightwave Technology, vol. 36, no. 16, 3427–3433, 2018.
  * [20] S.-K. Liao, W.-Q. Cai, W.-Y. Liu, L. Zhang, Y. Li, J.-G. Ren, J. Yin, Q. Shen, Y. Cao, Z.-P. Li, et al., “Satellite-to-Ground Quantum Key Distribution,” Nature, vol. 549, no. 7670, 43–47, 2017.
  * [21] D. Lin, D. Huang, P. Huang, J. Peng, and G. Zeng, “High Performance Reconciliation for Continuous-Variable Quantum Key Distribution with LDPC Code,” International Journal of Quantum Information, vol. 13, no. 02, 1550010, 2015.
  * [22] X. Wang, Y. Zhang, S. Yu, B. Xu, Z. Li, and H. Guo, “Efficient Rate-Adaptive Reconciliation for Continuous-Variable Quantum Key Distribution,” Quantum Information & Computation, vol. 17, no. 13–14, 1123–1134, 2017.
  * [23] C. Zhou, X. Wang, Y. Zhang, Z. Zhang, S. Yu, and H. Guo, “Continuous-Variable Quantum Key Distribution with Rateless Reconciliation Protocol,” Physical Review Applied, vol. 12, no. 5, 054013, 2019.
  * [24] M. Milicevic, C. Feng, L. M. Zhang, and P. G. Gulak, “Quasi-Cyclic Multi-Edge LDPC Codes for Long-Distance Quantum Cryptography,” NPJ Quantum Information, vol. 4, no. 1, 1–9, 2018.
  * [25] S.-S. Yang, Z.-G. Lu, and Y.-M. Li, “High-Speed Post-Processing in Continuous-Variable Quantum Key Distribution Based on FPGA Implementation,” Journal of Lightwave Technology, vol. 38, no. 15, 3935–3941, 2020.
  * [26] H. Li and Y. Pang, “FPGA-Accelerated Quantum Computing Emulation and Quantum Key Distillation,” IEEE Micro, vol. 41, no. 4, 49–57, 2021\.
  * [27] C. Weedbrook, A. M. Lance, W. P. Bowen, T. Symul, T. C. Ralph, and P. K. Lam, “Quantum Cryptography without Switching,” Physical Review Letters, vol. 93, no. 17, 170504, 2004.
  * [28] N. Hosseinidehaj, A. M. Lance, T. Symul, N. Walk, and T. C. Ralph, “Finite-Size Effects in Continuous-Variable Quantum Key Distribution with Gaussian Postselection,” Physical Review A, vol. 101, no. 5, 052335, 2020.
  * [29] D. Dequal, L. T. Vidarte, V. R. Rodriguez, G. Vallone, P. Villoresi, A. Leverrier, and E. Diamanti, “Feasibility of Satellite-to-Ground Continuous-Variable Quantum Key Distribution,” NPJ Quantum Information, vol. 7, no. 1, 1–10, 2020.
  * [30] M. Bloch, A. Thangaraj, and S. W. McLaughlin, “Efficient Reconciliation of Correlated Continuous Random Variables Using LDPC Codes,” arXiv preprint cs/0509041, 2005.
  * [31] P. Jouguet, D. Elkouss, and S. Kunz-Jacques, “High-Bit-Rate Continuous-Variable Quantum Key Distribution,” Physical Review A, vol. 90, no. 4, 042329, 2014.
  * [32] H. Mani, T. Gehring, P. Grabenweger, B. Ömer, C. Pacher, and U. L. Andersen, “Multiedge-Type Low-Density Parity-Check Codes for Continuous-Variable Quantum Key Distribution,” Physical Review A, vol. 103, no. 6, 062419, 2021.
  * [33] H. Imai and S. Hirakawa, “A New Multilevel Coding Method Using Error-Correcting Codes,” IEEE Transactions on Information Theory, vol. 23, no. 3, 371–377, 1977.
  * [34] U. Wachsmann, R. F. Fischer, and J. B. Huber, “Multilevel codes: Theoretical concepts and practical design rules,” IEEE Transactions on Information Theory, vol. 45, no. 5, 1361–1391, 1999.
  * [35] R. D. Wesel, X. Liu, J. M. Cioffi, and C. Komninakis, “Constellation Labeling for Linear Encoders,” IEEE Transactions on Information Theory, vol. 47, no. 6, 2417–2431, 2001.
  * [36] M. Bloch, A. Thangaraj, S. W. McLaughlin, and J.-M. Merolla, “LDPC-Based Gaussian Key Reconciliation,” in IEEE Information Theory Workshop-ITW’06 Punta del Este, 116–120, IEEE, 2006.
  * [37] A. Leverrier, R. Alléaume, J. Boutros, G. Zémor, and P. Grangier, “Multidimensional Reconciliation for a Continuous-Variable Quantum Key Distribution,” Physical Review A, vol. 77, no. 4, 042325, 2008\.
  * [38] J. Fiurášek and N. J. Cerf, “Gaussian Postselection and Virtual Noiseless Amplification in Continuous-Variable Quantum Key Distribution,” Physical Review A, vol. 86, no. 6, 060302, 2012.
  * [39] F. Darema, “The SPMD Model: Past, Present and Future,” in European Parallel Virtual Machine/Message Passing Interface Users’ Group Meeting, 1–1, Springer, 2001.
  * [40] M. Pharr and W. R. Mark, “A SPMD Compiler for High-Performance CPU Programming,” in Innovative Parallel Computing (InPar), 1–13, IEEE, 2012\.
  * [41] J. Lodewyck, M. Bloch, R. García-Patrón, S. Fossier, E. Karpov, E. Diamanti, T. Debuisschert, N. J. Cerf, R. Tualle-Brouri, S. W. McLaughlin, et al., “Quantum Key Distribution over 25 km with an All-Fiber Continuous-Variable System,” Physical Review A, vol. 76, no. 4, 042305, 2007.
  * [42] F. Laudenbach, C. Pacher, C.-H. F. Fung, A. Poppe, M. Peev, B. Schrenk, M. Hentschel, P. Walther, and H. Hübel, “Continuous-Variable Quantum Key Distribution with Gaussian Modulation—The Theory of Practical Implementations,” Advanced Quantum Technologies, vol. 1, no. 1, 1800011, 2018.
  * [43] Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel Coding Rate in the Finite Blocklength Regime,” IEEE Transactions on Information Theory, vol. 56, no. 5, 2307–2359, 2010.
  * [44] D. Slepian and J. Wolf, “Noiseless Coding of Correlated Information Sources,” IEEE Transactions on Information Theory, vol. 19, no. 4, 471–480, 1973.
  * [45] T. Richardson and R. Urbanke, Modern Coding Theory.  Cambridge University Press, 2008.
  * [46] X. Ai, R. Malaney, and S. X. Ng, “A Reconciliation Strategy for Real-Time Satellite-Based QKD,” IEEE Communications Letters, vol. 24, no. 5, 1062–1066, 2020.
  * [47] S.-Y. Chung, T. J. Richardson, and R. L. Urbanke, “Analysis of Sum-Product Decoding of Low-Density Parity-Check Codes Using a Gaussian Approximation,” IEEE Transactions on Information Theory, vol. 47, no. 2, 657–670, 2001.
  * [48] V. A. Chandrasetty and S. M. Aziz, “FPGA Implementation of an LDPC Decoder Using a Reduced Complexity Message Passing Algorithm,” Journal of Networks, vol. 6, no. 1, 36, 2011.
  * [49] A. Leverrier, “Composable Security Proof for Continuous-Variable Quantum Key Distribution with Coherent States,” Physical Review Letters, vol. 114, no. 7, 070501, 2015.
  * [50] C. Lupo, C. Ottaviani, P. Papanastasiou, and S. Pirandola, “Continuous-Variable Measurement-Device-Independent Quantum Key Distribution: Composable Security against Coherent Attacks,” Physical Review A, vol. 97, no. 5, 052327, 2018.
  * [51] N. Hosseinidehaj, N. Walk, and T. C. Ralph, “Optimal Realistic Attacks in Continuous-Variable Quantum Key Distribution,” Physical Review A, vol. 99, no. 5, 052336, 2019.
  * [52] S. Pirandola, “Limits and Security of Free-Space Quantum Communications,” Physical Review Research, vol. 3, no. 1, 013279, 2021\.
  * [53] S. Pirandola, “Satellite Quantum Communications: Fundamental Bounds and Practical Security,” Physical Review Research, vol. 3, no. 2, 023130, 2021.
  * [54] J. H. Mathews and K. D. Fink, Numerical Methods Using MATLAB, vol. 4.  Pearson Prentice Hall Upper Saddle River, NJ, 2004.
  * [55] A. Leverrier, “Security of Continuous-Variable Quantum Key Distribution via a Gaussian de Finetti Reduction,” Physical Review Letters, vol. 118, no. 20, 200501, 2017.
  * [56] E. Villaseñor, R. Malaney, K. A. Mudge, and K. J. Grant, “Atmospheric Effects on Satellite-to-Ground Quantum Key Distribution Using Coherent States,” in GLOBECOM 2020-2020 IEEE Global Communications Conference, 1–6, IEEE, 2020.
  * [57] J. Mateo, Efficient Information Reconciliation for Quantum Key Distribution.  PhD thesis, Universidad Politecnica de Madrid, 2011.
  * [58] T. Tian, C. R. Jones, J. D. Villasenor, and R. D. Wesel, “Selective Avoidance of Cycles in Irregular LDPC Code Construction,” IEEE Transactions on Communications, vol. 52, no. 8, 1242–1247, 2004.
  * [59] D. V. Nguyen, S. K. Chilappagari, M. W. Marcellin, and B. Vasic, “On the Construction of Structured LDPC Codes Free of Small Trapping Sets,” IEEE Transactions on Information Theory, vol. 58, no. 4, 2280–2302, 2012.
  * [60] S. Landner and O. Milenkovic, “Algorithmic and Combinatorial Analysis of Trapping Sets in Structured LDPC Codes,” in International Conference on Wireless Networks, Communications and Mobile Computing, vol. 1, 630–635, IEEE, 2005.
  * [61] X. Wang, Y. Zhang, S. Yu, and H. Guo, “High Speed Error Correction for Continuous-Variable Quantum Key Distribution with Multi-Edge Type LDPC Code,” Scientific Reports, vol. 8, no. 1, 1–7, 2018\.
  * [62] Y. Li, X. Zhang, Y. Li, B. Xu, L. Ma, J. Yang, and W. Huang, “High-Throughput GPU Layered Decoder of Quasi-Cyclic Multi-Edge Type Low Density Parity Check Codes in Continuous-Variable Quantum Key Distribution Systems,” Scientific Reports, vol. 10, no. 1, 1–11, 2020.
  * [63] F. Grosshans, “Collective Attacks and Unconditional Security in Continuous Variable Quantum Key Distribution,” Physical Review Letters, vol. 94, 020504, 2005.
  * [64] M. Navascués, F. Grosshans, and A. Acin, “Optimality of Gaussian Attacks in Continuous-Variable Quantum Cryptography,” Physical Review Letters, vol. 97, no. 19, 190502, 2006.
  * [65] S. Fossier, E. Diamanti, T. Debuisschert, R. Tualle-Brouri, and P. Grangier, “Improvement of Continuous-Variable Quantum Key Distribution Systems by Using Optical Preamplifiers,” Journal of Physics B: Atomic, Molecular and Optical Physics, vol. 42, no. 11, 114014, 2009.
  * [66] P. Jouguet, S. Kunz-Jacques, E. Diamanti, and A. Leverrier, “Analysis of Imperfections in Practical Continuous-Variable Quantum Key Distribution,” Physical Review A, vol. 86, no. 3, 032309, 2012.

In this appendix, we elaborate on the estimation of channel parameters, $T$
and $\xi_{ch}$, from $N_{e}$ quantum signals and determination of the upper
bound of $S_{BE}^{\epsilon_{PE}}$ based on the estimated $T$ and $\xi_{ch}$
for a given $N$. Here, we closely follow the methodology in [17] (and
references therein).

The parameter estimation at Step 4 of our protocol is a two-step process.
Firstly, Alice and Bob estimate each coefficient in the covariance matrix
between the shared states based on $N_{e}$ (randomly selected) quantum signals
sent from Bob. Then Alice uses these estimated coefficients to determine $T$
and $\xi_{ch}$. In the asymptotic regime, the estimation of $T$ and $\xi_{ch}$
is exact since Alice and Bob use an infinite number of quantum signals. The
following the two functions will be useful,

$\displaystyle
F_{1}(v_{1},v_{2})=\sqrt{\frac{v_{1}+\sqrt{v_{1}^{2}-4v_{2}}}{2}}\,,$ (33)
$\displaystyle
F_{2}(v_{1},v_{2})=\sqrt{\frac{v_{1}-\sqrt{v_{1}^{2}-4v_{2}}}{2}}\,.$ (34)

Alice can determine the Holevo Information between Bob and Eve’s states
$\chi_{EB}$ via[63, 64, 65]

$\chi_{EB}=\chi_{E}-\chi_{E|B}\,,$ (35)

where $\chi_{E}$ is Eve’s von Neumann Entropy before Bob makes his heterodyne
detection and $\chi_{E|B}$ is Eve’s von Neumann Entropy after his detection.
The term $\chi_{E}$ is given by

$\chi_{E}=Z\left(\frac{\psi_{1}-1}{2}\right)+Z\left(\frac{\psi_{2}-1}{2}\right)\,,$
(36)

where

$Z(z)=(z+1)\log{(z+1)}-z\log{z}\,.$ (37)

We define that $\psi_{1}=F_{1}(\Psi_{1},\Psi_{2})$ and
$\psi_{2}=F_{2}(\Psi_{1},\Psi_{2})$ to be the symplectic eigenvalues of the
covariance matrix of the shared states (before Bob’s heterodyne detection)
where

$\displaystyle\Psi_{1}=(V_{A}+1)^{2}(1-2T)+2T+T^{2}\left(V_{A}+1+\chi_{ch}\right)\,,$
(38) $\displaystyle\Psi_{2}=T^{2}\left((V_{A}+1)\xi_{ch}+1\right)\,,$ (39)
$\displaystyle\chi_{ch}=\frac{1-T}{T}+\xi_{ch}\,.$ (40)

The term $\chi_{E|B}$ is given by

$\chi_{E|B}=Z\left(\frac{\theta_{1}-1}{2}\right)+Z\left(\frac{\theta_{2}-1}{2}\right)+Z\left(\frac{\theta_{3}-1}{2}\right)\,,$
(41)

where $\theta_{1}$, $\theta_{2}$ and $\theta_{3}$ are the symplectic
eigenvalues of the covariance matrix of the shared states (after Bob’s
heterodyne detection). Specifically, we have
$\theta_{1}=F_{1}\left(\Theta_{1},\Theta_{2}\right)$ and
$\theta_{2}=F_{2}\left(\Theta_{1},\Theta_{2}\right)$ where

$\displaystyle\begin{aligned}
\Theta_{1}=&\bigg{(}\Psi_{1}\chi^{2}_{d}+\Psi_{2}+1\bigg{.}\\\
&\bigg{.}+2\chi_{d}\left(T\left(V_{A}+1+\chi_{ch}\right)+\left(V_{A}+1\right)\sqrt{\Psi_{2}}\right)\bigg{.}\\\
&\bigg{.}+2T\left(V_{A}^{2}+2V_{A}\right)\bigg{)}\frac{1}{T^{2}\left(V_{A}+1+\chi\right)}\,,\\\
\end{aligned}$ (42)
$\displaystyle\Theta_{2}=\left(\frac{V_{A}+1+\chi_{d}\sqrt{\Psi_{2}}}{T\left(V_{A}+1+\chi\right)}\right)^{2}\,,$
(43)
$\displaystyle\chi_{d}=\frac{2-\eta_{d}}{\eta_{d}}+\frac{2\chi_{d}}{\eta_{d}}\,,$
(44) $\displaystyle\chi=\chi_{ch}+\frac{\chi_{d}}{T}\,,$ (45)

where $\eta_{d}$ is the detection efficiency and we set $\eta_{d}=1$ for
simplicity. It is known that $\theta_{3}=1$ under the assumption of Gaussian
collective attack[65]. Therefore, we have
$Z\left(\frac{\theta_{3}-1}{2}\right)=0$.

However, the estimation of $T$ and $\xi_{ch}$ is not exact in the finite-key
regime. The estimated $T$ and $\xi_{ch}$ are subject to statistical
fluctuations that leads to a deviation of the estimated $T$ and $\xi_{ch}$
from their true values (since Alice and Bob use only $N_{e}$ signals for the
estimation at Step 4). The impact of using a finite number of quantum signals
for parameter estimation in the security analysis is twofold. Firstly, the
protocol will fail with a probability of $\epsilon_{PE}$ if the true value of
$T$ or $\xi_{ch}$ is out of the confidence interval set by that
$\epsilon_{PE}$. Secondly, the amount of the deviation of the estimated $T$
and $\xi_{ch}$ from their true values is probabilistic. The lower and upper
limits of the confidence interval of the estimated $T$ for a given
$\epsilon_{PE}$ are given by[15, 66]

$\displaystyle
T^{L}=\left(\hat{t}-\tau_{\epsilon_{PE}/2}\sqrt{\frac{\hat{\sigma}^{2}}{N_{e}V_{A}}}\right)^{2}\,,$
(46) $\displaystyle
T^{U}=\left(\hat{t}+\tau_{\epsilon_{PE}/2}\sqrt{\frac{\hat{\sigma}^{2}}{N_{e}V_{A}}}\right)^{2}\,,$
(47)

where $\tau_{\epsilon_{PE}/2}=Q^{-1}(\frac{\epsilon_{PE}}{2})$; and $\hat{t}$
and $\hat{\sigma}$ are the estimators for $T$ and $\xi_{ch}$, respectively.
Similarly, the lower and upper limits of the confidence interval of the
estimated $\xi_{ch}$ for a given $\epsilon_{PE}$ are given by[15, 66]

$\displaystyle\xi_{ch}^{L}=\frac{\hat{\sigma}^{2}-\tau_{\epsilon_{PE}/2}\frac{\hat{\sigma}^{2}\sqrt{2}}{\sqrt{N_{e}}}+1+\xi_{d}}{\hat{t}^{2}}\,,$
(48)
$\displaystyle\xi_{ch}^{U}=\frac{\hat{\sigma}^{2}+\tau_{\epsilon_{PE}/2}\frac{\hat{\sigma}^{2}\sqrt{2}}{\sqrt{N_{e}}}-1-\xi_{d}}{\hat{t}^{2}}\,,$
(49)

respectively.

Based on the above, we can now determine $S_{BE}^{\epsilon_{PE}}$, i.e. the
upper bound of $\chi_{BE}$ in the finite-key regime. Firstly, for the purpose
of analysis, we set the expectation of $\hat{t}$ and $\hat{\sigma}$ as
$\sqrt{\eta_{d}T}$ and $T\eta_{d}\xi_{ch}+1+\xi_{d}$, repectively. Then, we
replace $T$ and $\xi_{ch}$ in Eqs. 38 to 40 and Eqs. 42 to 45 with $T^{L}$ and
$\xi_{ch}^{U}$, respectively. Next, we determine $S_{BE}^{\epsilon_{PE}}$ by
using Eqs. 33, 34 to determine all the symplectic eigenvalues. Finally, we use
Eq. 36, 41 and 35 to obtain $S_{BE}^{\epsilon_{PE}}$.

Figure 8: $K$ (in bits per pulse) vs. $N_{e}$. Here we adopt the standard CV-
QKD setting except for $N_{o}$ for all the curves. For all the curves, we
assume $N_{e}=\frac{N_{o}}{2}$.

The motivation of setting a large $N_{e}$ is to reduce the length of the
confidence intervals when estimating $T$ and $\xi_{ch}$. In Fig. 8, we compare
the impact on $K$ when setting different $N_{e}$. For all the curves in Fig.
8, we assume $N_{e}=\frac{N_{o}}{2}$ (see Section V-C for the case of varying
$N_{e}$ for a given $N_{o}$). The “take-away” message is that, for a given
$\epsilon$, setting a large $N_{e}$ is necessary for most CV-QKD deployments
if a significant reduction of $K$ is to be avoided.


11institutetext: ∗ Sorbonne Université, CNRS, LIP6, F-75005 Paris, France
∗∗ Université Paul Sabatier, IRIT, Toulouse, France
{hanane.djeddal, thomas.gerald<EMAIL_ADDRESS>
{sauvagnat<EMAIL_ADDRESS>

# Does Structure Matter? Leveraging Data-to-Text Generation for Answering
Complex Information Needs

Hanane Djeddal∗ Thomas Gerald∗ Laure Soulier∗
Karen Pinel-Sauvagnat∗∗ Lynda Tamine∗∗

###### Abstract

In this work, our aim is to provide a structured answer in natural language to
a complex information need. Particularly, we envision using generative models
from the perspective of data-to-text generation. We propose the use of a
content selection and planning pipeline which aims at structuring the answer
by generating intermediate plans. The experimental evaluation is performed
using the TREC Complex Answer Retrieval (CAR) dataset. We evaluate both the
generated answer and its corresponding structure and show the effectiveness of
planning-based models in comparison to a text-to-text model.

###### keywords:

Answer generation, Complex search tasks, Data-to-text generation

Figure 1: Example of a query from the CAR dataset [6] and variants of outputs
(structured or plain answers) obtained using a sequential DTT planning-based
model.

##  1 Introduction

Complex search tasks (e.g., exploratory) involve open-ended and multifaceted
queries that require information retrieval (IR) systems to aggregate
information over multiple unstructured documents [19]. To address these
requirements, most interactive IR methods adopt the dynamic multi-turn
retrieval approach by designing session-based predictive models relying on
Markov models [21], query-flow graphs [7] for relevance prediction and
sequence-to-sequence models for query suggestion [15, 1]. One drawback of
those approaches remains in the iterative querying process, requesting users
to visit different contents to complete their information need. Moreover,
while there is a gradual shift today towards new interaction paradigms through
natural-sounding answers [5, 16], most approaches still rely on a ranked list
of documents as the main form of answer.

In this paper, we envision solving complex search tasks triggered by open-
ended queries, by considering single-turn (vs. multi-turn) interaction with
users and providing natural language generated answers (vs. a ranked list of
documents). We focus on the upstream part of the search process, once a ranked
list of candidate documents has been identified in response to a complex
information need. In a close line of research, open-domain QA attempt to
retrieve and reason over multiple seed passages either to extract [2, 4] or to
generate in a natural language form [14, 18, 16] answers to open-domain
questions. Most open-domain QA approaches adopt the ”Retriever Reader”
framework: the retriever ranks candidate passages, then the reader constructs
the response based on the most relevant retrieved candidate [9, 17, 24].
Compared with open-domain QA, answer generation to open-ended queries has two
main specific issues: 1) all the documents provided by the reader potentially
contribute both as evidence and source to generate the answer leading to
difficulties in discriminating between relevance and salience of the spans; 2)
while most QA problems target a single-span answer [22] included in one
document, open-ended queries are characterized by multiple facets [19, 20]
that could target a multiple-span answer.
Our objective is to generate an answer that covers the multiple facets of an
open-ended query using as input, an initial ranked list of documents. We
basically assume that the list of documents cover the different query facets.
A naive approach would be to exploit text-to-text models [12, 11]. However, we
believe that answering multi-faceted queries would require the modelling of
structure prior to generating the answer’s content111As outlined in the Swirl
report [5], regarding the importance of structure in the ”Generation of
Information Objects” (GIOs). To fit with this requirement, we adopt a data-to-
text (DTT) generation approach [10] that introduces the notion of structure by
guiding the generation with an intermediary plan aiming at determining what to
say on the basis of the input data. This intermediary step, called content
selection/planning, reinforces the factualness and the coverage of the
generated text since: 1) it organizes the data structure in a latent form to
better fit with the generated output, and 2) it provides a structure to the
generated answer based on the elements of the initial data. Figure 1 presents
an example of a query from TREC Complex Answer Retrieval (CAR) dataset [6] and
the two variants of answers (plain answers, structured answers) generated by
our proposed model trained respectively on two different train-test datasets
(See Section 3). To sum up, given a ranked list of documents relevant to a
complex information need, this work investigates the potential of content
selection and planning DTT generation models for single-turn answer
generation.

##  2 A data-to-text approach for answer generation

In this section, we introduce the model used for generating natural language
answers to open-ended queries formulated by users while completing complex
search tasks. The designed model is driven by the intuition that the response
should be guided by a structure to cover most of the query facets. This prior
is modeled through a hierarchical plan which corresponds to a textual object
relating the structure of the response with multiple-level titles (titles,
subtitles, etc).
More formally, we consider a document collection $\mathcal{D}$ and a set
$Q\times A\times P$ of query-answer-plan triplets, where $q\in Q$ refer to
queries, answers $a\in A$ the final response in natural language provided to
the user and plans $p\in P$ represent the hierarchical structure of answers
$a$. All documents $d$, queries $q$, answers $a$ are represented by sets of
tokens. For modeling the structure of plans $p$, we use
$p=\\{h_{1},...,h_{i},...,h_{|p|}\\}$ where $h_{i}$ represents a line in the
plan expressing a heading (title, subtitles, etc.). The $h_{i}$ are modeled as
sets of tokens.
Given a query $q$ and a document collection $\mathcal{D}$, our objective is to
generate an answer $a$. To do so, we follow the ”Retriever Generator”
framework in which: 1) a ranking model $\mathcal{M}_{ret}$ retrieves a ranked
list $\mathcal{D}_{q}$ of documents in response to query $q$, where
$\mathcal{D}_{q}=\\{d_{q}^{1},\dots,d_{q}^{n}\\}$ and 2) a text generation
model $\mathcal{M}_{gen}$ generates answer $a$ given the retrieved list
$\mathcal{D}_{q}$ and query $q$. As outlined earlier, the challenges of our
task mainly rely on aggregating information over the ranked list of documents
and generating a structured answer in natural language. Thus, we fix the
retrieval model $\mathcal{M}_{ret}$ and focus on the generation model
$\mathcal{M}_{gen}$. The latter exploits the DTT generation model based on
content selection and planning [10]. To generate the intermediary plan $p$ and
the answer $a$, we rely on two successive encoder-decoders (based on T5 [12]
as the building-box model):
$\bullet$ The planning encoder-decoder encodes each document
$d_{q}\in\mathcal{D}_{q}$ concatenated with the query $q$ and decodes a plan
$p$. The training of such network is guided by the auto-regressive generation
loss:

$\mathcal{L}_{planning}(q,p)=P(p|q,\mathcal{D}_{q})=\prod_{j=1}^{|p|}\prod_{k=1}^{|h_{j}|}P(h_{jk}|h_{j,<k},q,\mathcal{D}_{q})$
(1)

where $j$ and $k$ point out resp. to the heading $h_{j}$ and the $k^{th}$
token $h_{jk}$ in heading $h_{j}$. $h_{j,<k}$ corresponds to the token
sequence in heading $h_{j}$ before the $k^{th}$ token.
$\bullet$ The content generation encoder-decoder encodes each heading $h_{p}$
in the plan $p$ (generated by the planning encoder-decoder) concatenated with
the embedding of the document list $\mathcal{D}_{q}$. The latter is obtained
by the planning encoder-decoder since the T5 model provides embeddings for
both documents independently and the set of documents. After the encoding, the
network then decodes an answer $a$. The training is also guided by the auto-
regressive generation loss:

$\mathcal{L}_{answer}(q,a,p)=P(a|q,p,\mathcal{D}_{q})=\prod_{k=1}^{|a|}P(a_{k}|a_{<k},q,p,\mathcal{D}_{q})$
(2)

where $a_{k}$ and $a_{<k}$ resp. express the $k^{th}$ token in answer $a$ and
the token sequence of answer $a$ before the $k^{th}$ token.
The final loss is then a combination of both auto-regressive losses:

$\mathcal{L}=\sum_{\\{q,a,p\\}\in Q\times A\times
P}\mathcal{L}_{planning}(q,p)+\mathcal{L}_{answer}(q,a,p)$ (3)

##  3 Evaluation Setup

### Dataset.

We selected the TREC CAR (Complex Answer Retrieval) 2017 corpus [6]. This
dataset includes: (1) queries - denoting complex search tasks with multiple
facets, (2) plans - expressing the different expected facets, and (3)
paragraphs extracted from English Wikipedia - corresponding to texts
associated with plan sections. The TREC CAR task consists of retrieving the
paragraphs associated to each plan section to build a structured answer
combining both plan sections and paragraphs. We used these structured answers
as the final objective of our generation model given the queries; and the
plans as the structure prior. Due to the structure prior constraint, we
removed in the training set222The large train set was used for training, and
the Y1 benchmark test set for testing. answers without any plans. To compare
the models abilities to generate structured answers, we also evaluate a new
form of expected answer (plain answers) where structure is not taken into
account. For this aim, we built a new dataset upon the initial TREC CAR
dataset but only considering the paragraphs (without plans). Thus, we obtain
two versions of datasets (for structured answers and plain answers) which both
follow the original split of the TREC CAR dataset. Second, for computational
reasons, we reduced the number of entries in our training set by considering
only a half of Fold 0 of the original dataset. Also, due to the memory
constraints of generation models and the length of Wikipedia articles, we
reduced the document size by only keeping the first sentence of paragraphs.
Some statistics of the original dataset and our two adapted datasets are given
in Table 1.

Table 1: Statistics on the TREC CAR 2017 dataset and its adaptation for experiments. | Original dataset | Structured answers | Plain answers
---|---|---|---
|  Train |  Test |  Train |  Test |  Train |  Test
#answers |  598 308 |  132 |  46 224 |  132 |  46 224 |  132
#tokens/answers |  1376.48 |  5456.94 |  609.31 |  1724.63 |  449.21 |  1409.79
#headings/plan |  6.10 |  17.69 |  6.22 |  17.69 |  - |  -

### Model variants and baselines.

We implement two versions of our model333code available at
https://github.com/hanane-djeddal/Complex-Answer-Generation/:
$\bullet$ Planning-seq: a sequential model where the planning module (Equation
1) and the content generation module (Equation 2) are trained separately. At
inference, both modules are used sequentially.
$\bullet$ Planning-e2e: the end-to-end version of our model (Equation 3). The
content module is fed with the output embeddings of the planning module, and
document tokens.

Besides, we compare our models with two baselines: 1) the T5 model [12] which
is fine-tuned on each dataset, and 2) Ext, an extractive method where we
extract, for each sentence in the ground truth, a sentence in the input
supporting documents that maximizes the F1 score of BERTScore [23]. All models
consider for each topic a set of 10 relevant paragraphs ranked using BM25 as
input.

### Metrics.

To evaluate the quality of the generation, we consider three well-known
metrics: 1) the ROUGE-L mid metric (Rouge-P, Rouge-R, Rouge-F) [8] measuring
the exact match between the generated and the reference texts, 2) the
BERTScore [23] (the F1 score is reported) which computes similarity between
the generated and the gold reference text embeddings, 3) the QuestEval [13]
framework which relies on question answering models to assess whether a
summary contains all the source information: if the same questions are asked
to the generated and the reference texts, the produced answers should be
consistent.

To evaluate the model’s ability to generate structure (namely the plans), we
use the METEOR score [3] capturing how well-ordered the output words are.

##  4 Results

Table 2: Effectiveness of the answer generation. In bold are the highest metric value among the generation models (T5, Planning-seq, Planning-e2e). |  |  | # tokens | Rouge-P | Rouge-R | Rouge-F | BERTScore | QuestEval
---|---|---|---|---|---|---|---|---
structured |  answers | EXT | $898.22$ | $36.50$ | $26.99$ | $29.86$ | $85.50$ | $41.99$
T5 | $126.25$ | $\boldsymbol{76.19}$ | $08.41$ | $14.25$ | $\boldsymbol{84.95}$ | $39.06$
Planning-seq | $181.39$ | $62.94$ | $09.57$ | $15.36$ | $84.44$ | $37.47$
Planning-e2e | $203.48$ | $63.4$ | $\boldsymbol{10.21}$ | $\boldsymbol{16.09}$ | $84.91$ | $\boldsymbol{39.31}$
plain |  answers | EXT | 885.35 | $34.35$ | $26.73$ | $28.99$ | $86.30$ | $42.34$
T5 | $110.62$ | $\boldsymbol{78.05}$ | $09.24$ | $15.48$ | $85.51$ | $39.89$
Planning-seq | $163.58$ | $65.73$ | $10.34$ | $16.27$ | $84.29$ | $38.46$
Planning-e2e | $126.91$ | $75.92$ | $\boldsymbol{10.34}$ | $\boldsymbol{17.05}$ | $\boldsymbol{85.67}$ | $\boldsymbol{40.78}$

We perform the experimental evaluations w.r.t. two objectives. First, we
measure the effectiveness of the generated answers. Second, we provide a
thorough analysis of the generated plans.

### Answer generation effectiveness.

Table 2 reports the results of the different settings and models used for
generating answers. It is worth of recall that the EXT baseline does not
address the generation task and is built from the ground truth leading to
provide high value trends. With this in mind, we can outline the following
statements:
$\bullet$ Planning-based generation models are competitive regarding the T5
generation baseline: our models allow to generate longer answers (avg. 200
tokens), thus increasing the recall metric (Rouge-R). The smaller precision
(76.19 for T5, up to 63.4 for our models) does not hinder the semantic content
of the answer (see BERTScore and QuestEval values which are very close to the
EXT metrics). This suggests that our models are able to generate answers with
the adequate content, even if noisy at some points.
$\bullet$ One can see the general trend towards higher metrics for all models
in the plain answers setting compared to the structured answers setting (e.g.
Rouge-P reaching up to 78.05 vs. 76.15) over all models. The plain answers
setting is less difficult since the expected answer is not structured (only
composed of paragraphs); evaluation metrics are higher since the gold
reference is not based on both plans and paragraphs (as in the structured
answers setting). In the plain answers setting, our models are most effective
(with an advantage for Planning-e2e with, for instance 17.05 Rouge-F vs. 15.48
for T5). Even if the plain answers setting does not expect plans in the final
answer, our models generate an intermediary plan that guides the answer
generation. In contrast, T5 directly generates the answer. This reinforces our
intuition about the importance of structure prior for generating an answer to
a complex information need.
$\bullet$ Our end-to-end model seems more effective than the sequential one
(e.g., resp. 40.78 vs. 38.46 for the QuestEval metric), suggesting the
relevance of guiding the learning of the planning encoder-decoder by the
answer generation task.

Table 3: Analysis of the intermediate and final plans (resp. noted IP and FP) in our sequential and end-to-end planning-based models for the structured answers setting.  | #tokens | #heading | depth | Rouge-P | Rouge-R | Rouge-F | BERTScore | Meteor
---|---|---|---|---|---|---|---|---
T5 | FP | $1.41$ | $2.24$ | $1.14$ | $\boldsymbol{39.89}$ | $04.69$ | $07.69$ | $77.40$ | $3.24$
Planning-seq | IP | $1.83$ | $\boldsymbol{4.42}$ | $\boldsymbol{1.45}$ | $31.20$ | $\boldsymbol{8.29}$ | $\boldsymbol{11.51}$ | $\boldsymbol{81.25}$ | $\boldsymbol{5.97}$
FP | $\boldsymbol{1.88}$ | $4.11$ | $\boldsymbol{1.45}$ | $31.31$ | $7.93$ | $11.03$ | $80.49$ | $5.55$
Planning-e2e | IP | $1.57$ | $3.37$ | $1.15$ | $35.15$ | $07.34$ | $11.12$ | $81.21$ | $5.51$
FP | $1.64$ | $3.27$ | $1.16$ | $34.79$ | $06.38$ | $09.78$ | $80.70$ | $4.71$

### Analyses of the generated plans.

To get a deeper understanding of our model behavior regarding the structure
prior, we analyze the plans generated by the different encoder-decoders: the
intermediate one provided by the planning encoder-decoder and the final one
included in the final answer after the generation encoder-decoder (we simply
extracted headings of the structured answer - red and blue lines in Figure 1).
We report in Table 3 the different evaluation metrics presented in Section 4
to measure the quality of plans and add some plan statistics (the average
number of tokens for each plan section - #token; the number of generated plan
sections by query -#heading; the mean depth of plan sections i.e $i$ of
$h_{i}$ -depth). Comparison of intermediate and final plans obtained by our
models with the final one generated by T5 highlights that: 1) our plans are
longer and more complex (more tokens by plan section - up to 1.83 in average,
more and deeper headings - up to 4/5 headings in average), 2) our plans
generally cover more facets (higher recall), in correct order (higher Meteor)
with a better relevant semantics (higher BERTScore). The lowest precision (up
to 35.15 vs. 39.89 for the T5) might be explained by the plan sizes. Moreover,
the comparison of intermediate vs. final plans underlines a general trend
towards lower quality of plans in the final step (e.g., 11.51 vs. 11.03 for
Planning-seq in terms of Rouge-F). But the previous discussion on answer
effectiveness, and the higher performance of our models regarding T5) suggests
that there is a balance to reach between raw text and plan generation and that
the structure prior is however highly beneficial for generating a good answer.

##  5 Conclusion

Traditionally, IR approaches solving complex information needs focused on
leveraging multi-turn interactions to provide optimal rankings of candidate
documents at each turn. In this paper we have suggested alternative retrieval
models that do not rely on the interactive updating of queries and document
rankings as answers. We suggest one such alternative approach can be found
using data-to-text generation models to generate in a single-turn, a natural
language and structured answer. Experimental evaluation of a planning-based
DTT model using the TREC CAR dataset shows the potential of our intuition. We
believe that our work opens up novel areas of investigation including answer
generation and explanation in conversational systems for IR.

## Acknowledgement

We would like to thank projects ANR JCJC SESAMS (ANR-18- CE23-0001) and ANR
COST (ANR-18-CE23-0016) for supporting this work. This work was performed
using HPC resources from GENCI-IDRIS (Grant 2021-101681).

## References

  * [1] Ahmad, W.U., Chang, K., Wang, H.: Context attentive document ranking and query suggestion.  pp. 385–394. Proceedings of the 42nd International ACM SIGIR, SIGIR 2019 (2019)
  * [2] Asai, A., Hashimoto, K., Hajishirzi, H., Socher, R., Xiong, C.: Learning to retrieve reasoning paths over wikipedia graph for question answering.  International Conference on Learning Representations (2020)
  * [3] Banerjee, S., Lavie, A.: Meteor: An automatic metric for mt evaluation with improved correlation with human judgments.  pp. 65–72. Proceedings of the acl workshop on intrinsic and extrinsic evaluation measures for machine translation and/or summarization (2005)
  * [4] Chen, D., Fisch, A., Weston, J., Bordes, A.: Reading wikipedia to answer open-domain questions.  ACL (2017)
  * [5] Culpepper, J.S., Diaz, F., Smucker, M.D.: Research frontiers in information retrieval: Report from the third strategic workshop on information retrieval in lorne (SWIRL 2018).  SIGIR Forum (1), 34–90 (2018)
  * [6] Dietz, L., Verma, M., Radlinski, F., Craswell, N.: Trec complex answer retrieval overview.  TREC (2017)
  * [7] Hassan Awadallah, A., White, R.W., Pantel, P., Dumais, S.T., Wang, Y.M.: Supporting complex search tasks.  CIKM ’14, p. 829–838. Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, New York, NY, USA (2014)
  * [8] Lin, C.Y.: Rouge: A package for automatic evaluation of summaries.  pp. 74–81. Text summarization branches out (2004)
  * [9] Min, S., Zhong, V., Zettlemoyer, L., Hajishirzi, H.: Multi-hop reading comprehension through question decomposition and rescoring.  In: ACL (2019)
  * [10] Puduppully, R., Dong, L., Lapata, M.: Data-to-text generation with content selection and planning.  pp. 6908–6915. The Thirty-Third AAAI Conference on Artificial Intelligence, AAAI 2019 (2019)
  * [11] Radford, A., Narasimhan, K.: Improving language understanding by generative pre-training (2018)
  * [12] Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., Liu, P.J.: Exploring the limits of transfer learning with a unified text-to-text transformer.  Journal of Machine Learning Research 21(140), 1–67 (2020)
  * [13] Scialom, T., Dray, P.A., Gallinari, P., Lamprier, S., Piwowarski, B., Staiano, J., Wang, A.: Questeval: Summarization asks for fact-based evaluation.  arXiv (2021)
  * [14] Song, L., Wang, Z., Hamza, W., Zhang, Y., Gildea, D.: Leveraging context information for natural question generation.  In: M.A. Walker, H. Ji, A. Stent (eds.) Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 569–574. Association for Computational Linguistics (2018)
  * [15] Sordoni, A., Bengio, Y., Vahabi, H., Lioma, C., Grue Simonsen, J., Nie, J.Y.: A hierarchical recurrent encoder-decoder for generative context-aware query suggestion.  Association for Computing Machinery, CIKM ’15 (2015)
  * [16] Tan, C., Wei, F., Yang, N., Du, B., Lv, W., Zhou, M.: S-net: From answer extraction to answer synthesis for machine reading comprehension.  AAAI (2018)
  * [17] Tu, M., Wang, G., Huang, J., Tang, Y., He, X., Zhou, B.: Multi-hop reading comprehension across multiple documents by reasoning over heterogeneous graphs.  Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics ACL (2019)
  * [18] Wang, Y., Liu, K., Liu, J., He, W., Lyu, Y., Wu, H., Li, S., Wang, H.: Multi-passage machine reading comprehension with cross-passage answer verification.  CoRR (2018)
  * [19] White, R.W., Roth, R.A.: Exploratory Search: Beyond the Query-Response Paradigm.  Morgan & Claypool Publishers, [San Rafael, Calif.] (2009)
  * [20] Wildemuth, B.M., Freund, L.: Assigning search tasks designed to elicit exploratory search behaviors.  HCIR ’12. Proceedings of the Symposium on Human-Computer Interaction and Information Retrieval ACM (2012)
  * [21] Yang, H., Guan, D., Zhang, S.: The query change model: Modeling session search as a markov decision process.  ACM Trans. Inf. Syst. 33(4), 20:1–20:33
  * [22] Yang, Z., Qi, P., Zhang, S., Bengio, Y., Cohen, W., Salakhutdinov, R., Manning, C.D.: HotpotQA: A dataset for diverse, explainable multi-hop question answering.  pp. 2369–2380. Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing ACL (2018)
  * [23] Zhang, T., Kishore, V., Wu, F., Weinberger, K.Q., Artzi, Y.: Bertscore: Evaluating text generation with bert.  arXiv preprint (2019)
  * [24] Zhang, X., Zhan, K., Hu, E., Fu, C., Luo, L., Jiang, H., Jia, Y., Yu, F., Dou, Z., Cao, Z., Chen, L.: Answer complex questions: Path ranker is all you need.  SIGIR ’21, p. 449–458. ACM (2021)