# CVNN-based Channel Estimation and Equalization
in OFDM Systems Without Cyclic Prefix

Heitor dos Santos Sousa  Jonathan Aguiar Soares  Kayol Soares Mayer  and
Dalton Soares Arantes Heitor S. Sousa, Jonathan A. Soares, Kayol S. Mayer, and
Dalton S. Arantes are with the Digital Communications Laboratory – ComLab,
Department of Communications, School of Electrical and Computer Engineering,
University of Campinas – Unicamp, 13083-852 Campinas, SP, Brazil, e-mails:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In modern communication systems operating with Orthogonal Frequency-Division
Multiplexing (OFDM), channel estimation requires minimal complexity with one-
tap equalizers. However, this depends on cyclic prefixes, which must be
sufficiently large to cover the channel impulse response. Conversely, the use
of cyclic prefix (CP) decreases the useful information that can be conveyed in
an OFDM frame, thereby degrading the spectral efficiency of the system. In
this context, we study the impact of CPs on channel estimation with complex-
valued neural networks (CVNNs). We show that the phase-transmittance radial
basis function neural network offers superior results, in terms of required
energy per bit, compared to classical minimum mean-squared error and least
squares algorithms in scenarios without CP.

###### keywords:

Machine Learning, OFDM, Neural Network, CVNN.

##  1 Introduction

With the increasing demand for technologies such as massive machine-type
communications (mMTC), enhanced mobile broadband (eMBB), and ultra-reliable
and low latency communications (URLLC), higher data rates over tighter
bandwidths have never been so important [1]. In view of these demands, recent
telecommunications technologies (e.g., 5G and beyond) have become paramount to
support these services.

A key enabling technology in most current communication systems is orthogonal
frequency-division multiplexing (OFDM). Employing OFDM, communications systems
can convey information via multiple and closely spaced sub-carriers (i.e.,
narrowband subchannel frequencies). Besides the natural user multiplexing in
different frequencies, OFDM also provides advantages regarding intersymbol
interference (ISI) [2] and intercarrier interference (ICI) [3]. While the
former is simply avoided by using a cyclic prefix, the latter is only a
problem in dynamic channels or local oscillator mismatches with high carrier
frequency offsets (CFOs) [4].

In typical OFDM systems, to increase the useful data rate (not considering
channel coding), it is possible to reduce the pilot rate, extend the number of
subcarriers, or increase the modulation order. However, these solutions come
with their own set of issues. By reducing the pilot rate, the channel
estimation becomes less accurate, and the system becomes more susceptible to
rapid channel variations, such as those present in dynamic channels. By
extending the number of subcarriers while maintaining the same bandwidth (to
avoid interference in adjacent channels), there is an increase in both the
computational complexity and the clock speed required to process the
transmitted and received signals. Lastly, increasing the modulation order
degrades the bit error rate (BER) at the receiver.

Motivated by the widespread use of machine learning (ML) and bolstered by the
support of the universal approximation theorem of artificial neural networks
(ANNs) [5], several works have proposed ML-based algorithms for channel
estimation in OFDM systems [6, 7, 8, 9, 10, 11, 12]. Soares et al. [7]
extended a classical smoothing filter of channel estimation with principal
component analysis (PCA) to cut residual noise. Le et al. [8] improve the
least squares (LS) channel estimation results using fully connected deep
neural networks (DNNs), convolutional neural networks (CNNs), and
bidirectional long short-term memory (LSTM). Mei et al. [9] employed online
and linear ML-based channel estimation with low complexity and a fast
convergence rate. Jebur et al. [10] implemented an ML-based channel estimator
to track time-varying and frequency-selective channels with a small number of
pilots. Müller et al. [11] proposed a symbol timing recovery algorithm with
deep radial basis function (RBF) ANNs. Ye et al. [12] demonstrated the
potential of deep learning for joint channel estimation and signal detection
of OFDM systems without cyclic prefix (CP).

Apart from these real-valued ML algorithms, complex-valued neural networks
(CVNNs) have also presented promising results for telecommunications, such as
channel equalization, beamforming, channel estimation, and decoding [13, 14,
15, 16, 17, 18, 19]. As already demonstrated in the literature, compared with
real-valued neural networks (RVNNs), CVNNs have increased functionality,
better performance, and reduced training time [20, 21, 22]. Furthermore, CVNNs
also rely on the universal approximation theorem, as recently proved in [23].

In this context, this paper proposes an extension of [12] for OFDM channel
estimation and equalization using a CVNN, the phase-transmittance radial basis
function (PT-RBF) neural network, in a CP-free scenario to increase the useful
information rate. Unlike [12], in this work we do not take into account the
OFDM decoding since it can be easily handled with a low complexity fast
Fourier transform (FFT). Moreover, it reduces the search space, and,
consequently, the neural network complexity, i.e., a smaller number of layers
and neurons is necessary. This paper aims to demonstrate a suitable approach
to online channel estimation of OFDM without CP. It is important to note that,
similarly to this paper, Chu et al. [24] proposed a channel estimation
technique using a CVNN for optical systems operating with filter bank
multicarrier with offset quadrature amplitude modulation (FBMC/OQAM). However,
compared to OFDM, FBMC has a higher implementation complexity, and the absence
of a cyclic prefix (CP) is an intrinsic characteristic of this architecture.
To the best of our knowledge, it is the first work handling a CVNN for OFDM
channel estimation and equalization without CP.

The remainder of this paper is organized as follows. Section 2 discusses the
implemented OFDM communication scheme, and Section 3 the classical least
squares (LS) and minimum mean-square error (MMSE) channel estimation
algorithms. Section 4 describes the proposed PT-RBF channel estimation.
Section 5 presents the computational complexities of the proposed algorithm.
Section 6 presents the results of the proposed approach compared with LS and
MMSE channel estimation. Lastly, Section 7 concludes the paper.

##  2 OFDM System Model

Figure 1: Orthogonal frequency division multiplexing (OFDM) communication
architecture.

Fig. 1 illustrates the OFDM communication architecture considered in this
work. First, on the transmitter (Tx) side, the QAM symbols $q$ are
parallelized by an S/P block, mapping $\mathbb{C}\mapsto\mathbb{C}^{K}$, where
$K$ is the number of sub-carriers. Then, the $K$-parallel symbols feed the
pilot insertion block that, depending on the channel estimation scheme at the
receiver (Rx) side, inserts block- or comb-type pilots [25]. Next, an inverse
fast Fourier transform (IFFT) block converts data from the frequency domain to
the time domain. In the sequel, a cyclic prefix (CP) of length $N_{cp}$ is
inserted at the beginning of each IFFT output to mitigate the inter-symbol
interference (ISI) [12]. Finally, the resultant signal is serialized (i.e.,
$\mathbb{C}^{K+N_{cp}}\mapsto\mathbb{C}$) in the parallel to serial (P/S)
block and sent over the wireless channel.

Considering a sample-spaced multipath channel with $N_{ds}$ samples
$\mathbf{h}[n]\in\mathbb{C}^{N_{ds}}$, the baseband received signal is

$y[n]=\sum_{i=0}^{N_{ds}-1}h_{i+1}[n]x[n-i]+w[n],$ (1)

where $n$ is the discrete-time index, $x[n]\in\mathbb{C}$ is the transmitted
data, and $w[n]\sim\mathcal{C}\mathcal{N}(0,\,\sigma_{w}^{2})\in\mathbb{C}$ is
the additive white Gaussian noise (AWGN) at the receiver, with zero mean and
variance $\sigma_{w}^{2}$.

On the receiver side, the income signal is firstly parallelized by an S/P
block, mapping $\mathbb{C}\mapsto\mathbb{C}^{K+N_{cp}}$. Next, the cyclic
prefix is removed in the CPR block, and the resultant signal of dimension
$\mathbb{C}^{K}$ is converted to the frequency domain by a fast Fourier
transform (FFT) block. Afterward, the FFT output feeds the channel estimation
block, which estimates the channel for the equalization block. A P/S block
serializes the resulting signal to produce the estimated outputs $\hat{q}$.

##  3 Channel Estimation and Equalization

In this work, we consider block-type pilot arrangements for channel
estimation. In the frequency domain, we consider $x[k]$ the pilots before the
CP block at the Tx, and $y[k]$ the pilots after the FFT block at the Rx, with
the frequency domain index $k\in[1,2,\cdots,K]$. In addition, $h[k]$
corresponds to the channel related to the $k$-th subcarrier.

The LS estimator minimizes the square distance between $x[k]$ and $y[k]$ [26],
obtaining the channel estimation

$h_{LS}[k]=\frac{y[k]}{x[k]}.$ (2)

The MMSE estimator is obtained with second-order statistics of the channel
[26], to minimize the mean square error, as

$h_{MMSE}[k]=\sigma^{2}_{h}[k]\left(\sigma^{2}_{h}[k]|x[k]|^{2}+\sigma^{2}_{w}[k]\right)^{-1}x^{*}[k]y[k],$
(3)

in which $[\cdot]^{*}$ is the conjugate operator, $[\cdot]^{-1}$ is the
inverse operator, and $\sigma^{2}_{h}[k]$ and $\sigma^{2}_{w}[k]$ are the
variances of $h[k]$ and $w[k]$, respectively. Note that, besides the inherent
higher computational complexity compared with (2), the MMSE estimator is also
dependent on the channel statistics $\sigma^{2}_{h}[k]$.

In both LS and MMSE estimations, the equalization is performed, per
subcarrier, as

$\tilde{x}[k]=\frac{y[k]}{\tilde{h}[k]},$ (4)

where $\tilde{h}[k]=h_{LS}[k]$ or $\tilde{h}[k]=h_{MMSE}[k]$, depending on the
channel estimation method.

##  4 Proposed CVNN Channel Estimation and Equalization

Figure 2: Orthogonal frequency division multiplexing (OFDM) communication
architecture with the proposed CVNN-based channel estimation and equalization.
The CVNN block represents the PT-RBF neural network composed of three layers.

The proposed channel estimation and equalization with a CVNN are shown in Fig.
2. Unlike the usual channel estimation and equalization illustrated in Fig. 1,
the proposed ML scheme performs both tasks at the same time, in a joint
scheme. The CVNN block is composed of a PT-RBF neural network with three
layers. The input layer is fed with the FFT output vector $\mathbf{y}$. The
hidden layer maps $\mathbf{y}$ onto a nonlinear space, through $N_{n}$
neurons. The Gaussian kernel (i.e., activation function) of the $i$-th neuron
is

$\phi_{i}=\exp{\left[\Re\\{v_{i}\\}\right]}+\jmath\exp{\left[\Im\\{v_{i}\\}\right]},$
(5)

in which $v_{i}$ is the argument of the $i$-th Gaussian kernel, given by

$v_{i}=\frac{\|\Re\\{\mathbf{y}\\}-\Re\\{\boldsymbol{\upgamma}_{i}\\}\|^{2}_{2}}{\Re\\{\sigma^{2}_{i}\\}}+\jmath\frac{\|\Im\\{\mathbf{y}\\}-\Im\\{\boldsymbol{\upgamma}_{i}\\}\|^{2}_{2}}{\Im\\{\sigma^{2}_{i}\\}},$
(6)

where $\boldsymbol{\upgamma}_{i}\in\mathbb{C}^{K}$ is the center vector and
$\sigma^{2}_{i}\in\mathbb{C}$ is the variance of the $i$-th neuron. The
operators $\Re\\{\cdot\\}$ and $\Im\\{\cdot\\}$ return the real and imaginary
components, respectively. The Euclidean norm is denoted by $\|\cdot\|_{2}$.

In the output layer, the $k$-th equalized output data $\tilde{x}[k]$ is
obtained via a linear combination of the Gaussian kernels and the vector of
synaptic weights $\mathbf{w}_{k}\in\mathbb{C}^{N_{n}}$, as

$\tilde{x}[k]=\mathbf{w}_{k}^{T}\boldsymbol{\upphi},$ (7)

in which $[\cdot]^{T}$ is the transpose operator and
$\boldsymbol{\upphi}\in\mathbb{C}^{N_{n}}$ is the vector of Gaussian kernels.

The PT-RBF is optimized via the complex-valued backpropagation process, using
the stochastic gradient descent (SGD) [19]. For the sake of representation,
$m$ denotes the SGD iteration during a training epoch with $M$ attributes,
i.e., $M$-OFDM symbols from the preamble. As the PT-RBF neural network
utilized in this work has only one hidden layer, its update equations can be
simplified from the generalized model proposed in [18], as

$\mathbf{W}[m+1]=\mathbf{W}[m]+\eta_{w}\mathbf{e}[m]\boldsymbol{\upphi}^{H}[m],$
(8) $\mathbf{b}[m+1]=\mathbf{b}[m]+\eta_{b}\boldsymbol{\upphi}[m],$ (9)
$\boldsymbol{\Gamma}[m+1]=\boldsymbol{\Gamma}[m]+\eta_{\gamma}\Re\\{\boldsymbol{\updelta}[m]\\}\left[\Re\\{\mathbf{Y}_{m}\\}-\Re\\{\boldsymbol{\Gamma}[m]\\}\right]\\\
+\jmath\eta_{\gamma}\Im\\{\boldsymbol{\updelta}[m]\\}\left[\Im\\{\mathbf{Y}_{m}\\}-\Im\\{\boldsymbol{\Gamma}[m]\\}\right],$
(10)
$\boldsymbol{\upsigma}^{2}[m+1]=\boldsymbol{\upsigma}^{2}[m]+\eta_{\sigma}\Re\\{\boldsymbol{\updelta}[m]\\}\Re\\{\mathbf{v}[m]\\}\\\
+\jmath\eta_{\sigma}\Im\\{\boldsymbol{\updelta}[m]\\}\Im\\{\mathbf{v}[m]\\},$
(11)

where $\mathbf{v}\in\mathbb{C}^{N_{n}}$ is the vector of Gaussian kernel
arguments, $\mathbf{W}\in\mathbb{C}^{K\times N_{n}}$ is the matrix of synaptic
weights, $\mathbf{b}\in\mathbb{C}^{K}$ is the vector of bias,
$\boldsymbol{\Gamma}\in\mathbb{C}^{N_{n}\times K}$ is the matrix of center
vectors, and $\boldsymbol{\upsigma}^{2}\in\mathbb{C}^{N_{n}}$ is the vector of
center variances. The parameters $\eta_{w}$, $\eta_{b}$, $\eta_{\gamma}$, and
$\eta_{\sigma}$ correspond to the learning rate of $\mathbf{W}$, $\mathbf{b}$,
$\boldsymbol{\Gamma}$, and $\boldsymbol{\upsigma}^{2}$, respectively. The
operator $[\cdot]^{H}$ denotes the Hermitian.

For $\boldsymbol{\Gamma}$ and $\boldsymbol{\upsigma}^{2}$, the diagonal matrix
of local gradients $\boldsymbol{\updelta}\in\mathbb{C}^{N_{n}\times N_{n}}$ is
given as

$\boldsymbol{\updelta}[m]=\mathrm{diag}[\Re\\{\mathbf{W}^{H}[m]\mathbf{e}[m]\\}\odot\Re\\{\boldsymbol{\upphi}[m]\\}\oslash\Re\\{\boldsymbol{\upsigma}^{2}[m]\\}]\\\
+\jmath\mathrm{diag}[\Im\\{\mathbf{W}^{H}[m]\mathbf{e}[m]\\}\odot\Im\\{\boldsymbol{\upphi}[m]\\}\oslash\Im\\{\boldsymbol{\upsigma}^{2}[m]\\}],$
(12)

in which $\mathrm{diag}[\cdot]$ returns a square diagonal matrix with its
argument vector on the main diagonal, and $\odot$ and $\oslash$ denote the
Hadamard product and division, respectively. The error vector is given by
$\mathbf{e}[m]=\mathbf{x}_{m}-\mathbf{\tilde{x}}_{m}$, for the PT-RBF output
$\mathbf{\tilde{x}}_{m}$ with respect to the desired OFDM symbol
$\mathbf{x}_{m}$, in the preamble. In addition, $\mathbf{Y}_{m}$ is the
expanded matrix of OFDM input symbols

$\mathbf{Y}_{m}=\begin{bmatrix}\textbf{\text{---}}&\mathbf{y}^{T}_{m}&\textbf{\text{---}}\\\
\textbf{\text{---}}&\mathbf{y}^{T}_{m}&\textbf{\text{---}}\\\ &\vdots&\\\
\textbf{\text{---}}&\mathbf{y}^{T}_{m}&\textbf{\text{---}}\end{bmatrix}.$ (13)

##  5 Computational Complexities

In order to analyze the computational complexity of the proposed PT-RBF joint
channel estimation and equalization, we rely on the PT-RBF computational
complexity presented in [19] (see Table 3.7 on page 87). In this work, the
computational complexities are expressed in terms of the number of real-valued
multiplications and additions. To accomplish this, each complex-valued
multiplication is represented by four real-valued multiplications and two
additions, and each complex-valued addition is represented by two real-valued
additions. Based on [19], Table 1 depicts the computational complexities of
training and inference of the PT-RBF employed in this work.

Table 1: Computational complexities for training and inference of the PT-RBF for joint channel estimation and equalization. Stage | Additions | Multiplications
---|---|---
Training | $N_{n}(16K-2)+4K$ | $N_{n}(16K+14)+2K$
Inference | $N_{n}(8K-2)$ | $N_{n}(6K+2)$

Then, keeping the number of subcarriers $K=64$, Table 2 presents the PT-RBF
computational complexities depending on the number of neurons $N_{n}$.
Additions are described by $+$, and multiplications by $\times$.

Table 2: PT-RBF computational complexities for training and inference, keeping $K=64$ subcarriers. $N_{n}$ | Training | Inference
---|---|---
$+$ | $\times$ | $+$ | $\times$
256 | 261,888 | 265,856 | 130,560 | 98,816
512 | 523,520 | 531,584 | 261,120 | 197,632
1,024 | 1,046,784 | 1,063,040 | 522,240 | 395,264
2,048 | 2,093,312 | 2,125,952 | 1,044,480 | 790,528

For the sake of simplicity, in order to compare the computational complexity
of the proposed work with the joint channel estimation and decoding proposed
by Ye et al. [12], we only consider the number of real-valued multiplications
since it is the most onerous mathematical operation. The number of real-valued
multiplications of an RVNN with multiple fully-connected layers can be found
in [19] (see Table 2.1 on page 37). Unlike the work of Ye et al. [12], the PT-
RBF here presented does not implement decoding. Thus, for a fair comparison,
we add the FFT computation complexity to the PT-RBF one. The number of real-
valued multiplications of the FFT was obtained from [27] (see Table I on page
154, three-BF and length 64 results in $248$ real-valued multiplications).
Table 3 presents the computational complexities of the PT-RBF with FFT and the
DNNs proposed by Ye et al. [12] (8 RVNNs with five layers each, containing
256, 500, 250, 120, and 16 neurons, respectively). Note that, as Ye et al.
[12] handle two OFDM symbols at a time, we multiply the PT-RBF with FFT
computational complexity by two. The number of subcarriers is $K=64$ and the
PT-RBF is considered with $N_{n}=2,048$ neurons (the maximum number of neurons
implemented in this work).

Table 3: Computational complexities of the PT-RBF with FFT and the work of Ye et al. [12]. Stage | PT-RBF with FFT |  Ye et al. [12]
---|---|---
Training | 4,252,400 | 5,835,344
Inference | 1,581,552 | 2,279,360

From Table 3, in an equivalent scenario, the proposed approach has
approximately $30\%$ less complexity compared with the work of Ye et al. [12].
For a similar complexity, we could extend the PT-RBF to about $N_{n}=2,900$
neurons. Moreover, it is important to highlight that in the inference phase,
our approach generates $100\%$ of useful information since no pilot is
necessary. On the other hand, the useful information rate (not taking the CP
into account) of Ye et al. [12] is given by $100\times(N_{p}-K)/N_{p}$ $[\%]$,
where $N_{p}$ is the number of pilots per OFDM symbol. Then, for $K=64$
subcarriers and $N_{p}=8$ pilots, the useful information rate is $87.5\%$.
Consequently, the proposed approach presents a lower computational complexity
with a higher useful information rate.

##  6 Results

In order to represent a practical scenario, we set the simulation system with
the 3GPP TS 38.211 specification for 5G physical channels and modulation [28].
The OFDM is defined with 240 kHz subcarrier spacing, 64 active subcarriers,
and a block-based pilot scheme with a preamble of $5,000$ OFDM symbols.
Symbols are modulated with quadrature phase shift keying (QPSK).

Based on the tapped delay line-A (TDL-A) from the 3GPP TR 38.901 5G channel
models [29], the massive MIMO channel follows the TDLA100 from the 3GPP TR
38.104 5G radio base station transmission and reception [30]. The channel is
described with 12 taps, with varying delays from 0.0 ns to 290 ns and powers
from -26.2 dB to 0 dB. A Rayleigh distribution is used to compute the sample-
spaced multipath channel $\mathbf{h}[n]$.

The PT-RBF operates with 64 inputs and outputs and one hidden layer with
$N_{n}$ Gaussian neurons. The inputs are taken from the FFT outputs. The PT-
RBF outputs are equalized symbols. Each OFDM symbol from the preamble is
handled as a sample for training. The PT-RBF is trained for $200$ epochs with
a shuffle, to improve convergence. The learning rates were optimized, by trial
and error, as $\eta_{w}=0.02$, $\eta_{b}=0.02$, $\eta_{\gamma}=0.02$, and
$\eta_{\sigma}=0.01$.

Fig. 3 shows the results of the proposed PT-RBF for joint channel estimation
and the classical MMSE and LS algorithms. In this comparison, we have set
$N_{n}=2048$ neurons. It is important to highlight that, as results are
discussed in terms of bit energy to noise power spectral density ratio
($\mathrm{E_{b}}/\mathrm{N}_{0}$), we take the CP into account to plot the bit
error rate (BER). Also, we consider a pre-FEC (pre-forward error correction)
BER of $2\times 10^{-2}$ [31] for comparison. In the best-case scenario, with
a CP long enough to cover all channel impulses (17 samples), the PT-RBF
presented similar results with MMSE, and the LS achieved an inferior
performance of 2.91 dB. On the other hand, in the worst-case scenario (i.e.,
without CP), the PT-RBF approach presents better performance, surpassing the
MMSE and LS by about 2.68 dB and 10.51 dB, respectively. This better
performance follows the results demonstrated in [12], but with lower
computational complexity.

Figure 3: BER results of the proposed approach, MMSE, and LS channel
estimation algorithms with and without CP. Solid lines regard results without
CP and dashed lines with CP. Figure 4: PT-RBF joint channel estimation and
equalization results depending on the number of neurons $N_{n}$. Results
magnified for a BER $=2\times 10^{-2}$ to highlight performance.

Fig. 4 shows the PT-RBF performance without CP, depending on the number of
neurons $N_{n}$. In Fig. 4, we magnify the $\mathrm{E_{b}}/\mathrm{N}_{0}$
results for a BER $=2\times 10^{-2}$ for comparison. As expected, the
performance decays with $N_{n}$ reduction. However, reducing the number of
neurons by half, from $2,048$ to $1,024$, only impacts $0.37$ dB performance.
When reducing the complexity by one eighth (i.e., from $2,048$ to $256$
neurons), the $\mathrm{E_{b}}/\mathrm{N}_{0}$ is worsened by only $0.8$ dB.

##  7 Conclusions

This work proposes a complex-valued neural network (CVNN) for joint channel
estimation and equalization in OFDM systems without a cyclic prefix. Unlike
previous works in the literature, where neural networks were employed to
handle both channel estimation and decoding, we focus solely on addressing
channel imperfections. As a result, our neural network does not need to learn
the FFT decoding, thereby reducing its computational complexity. It is
preferable to keep the FFT mapping outside of the neural network since it can
be implemented with very low computational complexity. Our results demonstrate
that the proposed PT-RBF outperforms both MMSE and LS algorithms. Furthermore,
the computational complexity can be reduced by half at the cost of an
additional 0.37 dB. In future works, we plan to implement other well-known
CVNNs and to test for other system and channel imperfections, such as channel
dynamics and nonlinearities.

## References

  * [1] C.-W. Hsu and H.-S. Kim, “Hyper-dimensional modulation for robust short packets in massive machine-type communications,” _IEEE Transactions on Communications_ , vol. 71, no. 3, pp. 1388–1402, 2023.
  * [2] X.-G. Xia, “A new OFDM system for IIR channels,” _IEEE Wireless Communications Letters_ , pp. 1–4, 2023.
  * [3] M. Liao and Y. Zakharov, “Estimation of time-varying channels in virtual angular domain for massive MIMO systems,” _IEEE Access_ , vol. 11, pp. 1923–1933, 2023.
  * [4] N.-H. Cheng, K.-C. Huang, Y.-F. Chen _et al._ , “Maximum likelihood-based adaptive iteration algorithm design for joint CFO and channel estimation in MIMO-OFDM systems,” _EURASIP Journal on Advances in Signal Processing_ , vol. 2021, no. 1, pp. 1–21, 2021.
  * [5] K. Hornik, M. Stinchcombe, and H. White, “Multilayer feedforward networks are universal approximators,” _Neural Networks_ , vol. 2, no. 5, pp. 359–366, 1989.
  * [6] K. Mei, J. Liu, X. Zhang _et al._ , “Performance analysis on machine learning-based channel estimation,” _IEEE Transactions on Communications_ , vol. 69, no. 8, pp. 5183–5193, 2021.
  * [7] J. A. Soares, K. S. Mayer, P. B. Valadares, and D. S. Arantes, “PCA-based channel estimation for MIMO communications,” in _XL Simpósio Brasileiro de Telecomunicações e Processamento de Sinais (SBrT2022)_ , Sep. 2022, pp. 1–5.
  * [8] H. A. Le, T. Van Chien, T. H. Nguyen _et al._ , “Machine learning-based 5G-and-beyond channel estimation for MIMO-OFDM communication systems,” _Sensors_ , vol. 21, no. 14, pp. 1–23, 2021.
  * [9] K. Mei, J. Liu, X. Zhang _et al._ , “A low complexity learning-based channel estimation for OFDM systems with online training,” _IEEE Transactions on Communications_ , vol. 69, no. 10, pp. 6722–6733, 2021.
  * [10] B. A. Jebur, S. H. Alkassar, M. A. M. Abdullah _et al._ , “Efficient machine learning-enhanced channel estimation for OFDM systems,” _IEEE Access_ , vol. 9, pp. 100 839–100 850, 2021.
  * [11] C. Müller, K. S. Mayer, F. C. C. De Castro _et al._ , “Multilayer radial basis function neural network for symbol timing recovery,” _Neural Processing Letters_ , vol. 55, no. 3, pp. 3135–3148, 2023.
  * [12] H. Ye, G. Y. Li, and B.-H. Juang, “Power of deep learning for channel estimation and signal detection in OFDM systems,” _IEEE Wireless Communications Letters_ , vol. 7, no. 1, pp. 114–117, 2018.
  * [13] J. Liu, K. Mei, X. Zhang _et al._ , “Online extreme learning machine-based channel estimation and equalization for OFDM systems,” _IEEE Communications Letters_ , vol. 23, no. 7, pp. 1276–1279, 2019.
  * [14] K. S. Mayer, M. S. De Oliveira, C. Müller _et al._ , “Blind fuzzy adaptation step control for a concurrent neural network equalizer,” _Wireless Communications and Mobile Computing_ , vol. 2019, pp. 1–11, 2019\.
  * [15] M. P. Enriconi, F. C. C. De Castro, C. Müller _et al._ , “Phase transmittance RBF neural network beamforming for static and dynamic channels,” _IEEE Antennas and Wireless Propagation Letters_ , vol. 19, no. 2, pp. 243–247, 2020.
  * [16] K. S. Mayer, J. A. Soares, and D. S. Arantes, “Complex MIMO RBF neural networks for transmitter beamforming over nonlinear channels,” _Sensors_ , vol. 20, no. 2, pp. 1–15, 2020.
  * [17] J. A. Soares, K. S. Mayer, F. C. C. De Castro, and D. S. Arantes, “Complex-valued phase transmittance RBF neural networks for massive MIMO-OFDM receivers,” _Sensors_ , vol. 21, no. 24, pp. 1–31, 2021.
  * [18] K. S. Mayer, C. Müller, J. A. Soares, F. C. C. De Castro, and D. S. Arantes, “Deep phase-transmittance RBF neural network for beamforming with multiple users,” _IEEE Wireless Communications Letters_ , vol. 11, no. 7, pp. 1498–1502, 2022.
  * [19] K. S. Mayer, “Complex-valued neural networks and applications in telecommunications,” Ph.D. Thesis, University of Campinas, 2022. [Online]. Available: http://dx.doi.org/10.13140/RG.2.2.28044.80000/1
  * [20] A. Hirose and S. Yoshida, “Generalization characteristics of complex-valued feedforward neural networks in relation to signal coherence,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 23, no. 4, pp. 541–551, 2012.
  * [21] A. A. Cruz, K. S. Mayer, and D. S. Arantes, “RosenPy: An open source python framework for complex-valued neural networks,” _SSRN_ , pp. 1–18, 2022\. [Online]. Available: https://ssrn.com/abstract=4252610
  * [22] S.-Q. Zhang, W. Gao, and Z.-H. Zhou, “Towards understanding theoretical advantages of complex-reaction networks,” _Neural Networks_ , vol. 151, pp. 80–93, 2022.
  * [23] F. Voigtlaender, “The universal approximation theorem for complex-valued neural networks,” _Applied and Computational Harmonic Analysis_ , vol. 64, pp. 33–61, 2023.
  * [24] J. Chu, M. Gao, X. Liu _et al._ , “Channel estimation based on complex-valued neural networks in IM/DD FBMC/OQAM transmission system,” _Journal of Lightwave Technology_ , vol. 40, no. 4, pp. 1055–1063, 2022.
  * [25] S. Coleri, M. Ergen, A. Puri _et al._ , “Channel estimation techniques based on pilot arrangement in OFDM systems,” _IEEE Transactions on Broadcasting_ , vol. 48, no. 3, pp. 223–229, 2002.
  * [26] V. Savaux and Y. Louët, “LMMSE channel estimation in OFDM context: a review,” _IET Signal Processing_ , vol. 11, no. 2, pp. 123–134, 2017.
  * [27] H. Sorensen, M. Heideman, and C. Burrus, “On computing the split-radix FFT,” _IEEE Transactions on Acoustics, Speech, and Signal Processing_ , vol. 34, no. 1, pp. 152–156, 1986.
  * [28] “5G; NR; Physical channels and modulation,” ETSI, Sophia Antipolis, France, Tech. Rep. 38.211, Sep. 2022, (3GPP technical specification 38.211; version 17.3.0; release 17).
  * [29] “5G; Study on channel model for frequencies from 0.5 to 100 GHz,” ETSI, Sophia Antipolis, France, Tech. Rep. 38.901, Apr. 2022, (3GPP technical report 38.901; version 17.0.0; release 17).
  * [30] “5G; NR; Base station (BS) radio transmission and reception,” ETSI, Sophia Antipolis, France, Tech. Rep. 38.104, Oct. 2022, (3GPP technical specification 38.104; version 17.7.0; release 17).
  * [31] C. Castro, R. Elschner, T. Merkle _et al._ , “100 Gbit/s Terahertz-Wireless Real-Time Transmission Using a Broadband Digital-Coherent Modem,” in _Proc. 5G World Forum_. Dresden: IEEE, Nov 2019, pp. 399–402.


# Qubit-based clock synchronization for QKD systems using a Bayesian approach

Roderick D. Cochran<EMAIL_ADDRESS>Daniel J. Gauthier  Department of
Physics, The Ohio State University, Columbus, OH, 43210 USA

###### Abstract

Quantum key distribution (QKD) systems provide a method for two users to
exchange a provably secure key. Synchronizing the users’ clocks is an
essential step before a secure key can be distilled. Qubit-based
synchronization protocols directly use the transmitted quantum states to
achieve synchronization and thus avoid the need for additional classical
synchronization hardware. Previous qubit-based synchronization protocols
sacrifice secure key either directly or indirectly, and all known qubit-based
synchronization protocols do not efficiently use all publicly available
information published by the users. Here, we introduce a Bayesian
probabilistic algorithm that incorporates all published information to
efficiently find the clock offset without sacrificing any secure key.
Additionally, the output of the algorithm is a probability, which allows us to
quantify our confidence in the synchronization. For demonstration purposes, we
present a model system with accompanying simulations of an efficient three-
state BB84 prepare-and-measure protocol with decoy states. We use our
algorithm to exploit the correlations between Alice’s published basis and mean
photon number choices and Bob’s measurement outcomes to probabilistically
determine the most likely clock offset. We find that we can achieve a 95
percent synchronization confidence in only 4,140 communication bin widths,
meaning we can tolerate clock drift approaching 1 part in 4,140 in this
example when simulating this system with a dark count probability per
communication bin width of $8\times 10^{-4}$ and a received mean photon number
of 0.01.

##  I  Introduction

Introduced in 1984 [1], quantum key distribution (QKD) is a symmetric
encryption protocol that promises unconditional information security founded
on the fundamental laws of physics, rather than on the difficulty of
computational problems. Bennett and Brassard established the first QKD
protocol (BB84), which used the polarization degree of freedom of single
photons to transmit information. Subsequently developed protocols have
extended QKD to different types of systems [2] and relaxed the requirement for
a true single-photon source [3], paving the way for practical implementations
of quantum cryptography.

For the sake of concreteness, we consider a polarization-based prepare-and-
measure protocol. Here, one user (Alice) prepares and transmits a periodic
sequence of quantum states with period $\tau_{A}$ encoded in at least two
mutually unbiased orthonormal bases. In our example system, we use two bases:
horizontal/vertical (H/V) polarization and left circular/right (L/R) circular
polarization. We also use the decoy-state protocol where Alice occasionally
sends the vacuum quantum state. A second user (Bob), measures each quantum
state randomly in one of the two bases and records the result. After this
measurement phase is complete, Alice and Bob publish their basis choices for
each measurement and keep only the measurements where Bob registers a click
with his single-photon counting detectors and they use the same basis. This
process, called sifting, allows distilling a raw key, which, after error
correction and privacy amplification [4], becomes the secret classical key
securely shared between Alice and Bob. Our example system uses a pulsed
stochastic photonic source with decoy states [3], where the decoys are
photonic wavepackets with a lower mean photon number. To simplify the example
system and make it more efficient, we only transmit one state in the
monitoring basis, which gives an equivalent secure key rate in comparison to
transmitting both states in this basis [5, 6].

A practical issue in quantum communication protocols is synchronizing Alice
and Bob’s two data streams. If Bob does not know precisely when Alice begins
data transmission, he must begin recording measurements early or else risk
missing some of Alice’s transmission. In either case, because signals do not
arrive at Bob due to channel loss, and extraneous events are caused by stray
light and detector dark counts, the first event Bob records is unlikely to be
the first event Alice sends, resulting in some timing offset that must be
determined. Correcting this offset is an essential precursor to sifting: If
Alice and Bob do not agree on the timing of the events, they will compare
basis choices from different events, resulting in a high quantum bit error
rate (QBER) and likely share no information. In addition, determining which
time bins correspond to Alice’s wavepacket arrival and which do not allows
timing-based noise filtering.

Further complicating the communication protocol is that the relative clock
offset may not be a constant due to drift in the relative phase and frequency
between the transmitter and receiver clocks. Alice has a communication
protocol temporal bin width $\tau_{A}$ that may be different from Bob’s bin
width $\tau_{B}$. The timing offset between their clocks $\Delta$ at the
$n^{th}$ communication time bin since the most recent clock synchronization is
given by

$\Delta=t_{0}+(\tau_{A}-\tau_{B})n+\varepsilon$ (1)

for an initial timing offset $t_{0}$ and higher-order timing error
$\varepsilon$. In this way, small differences in clock frequencies can
gradually change the clock offset so that a previously calculated
synchronization is no longer valid. Other timing errors, such as clock jitter
and frequency drift, also contribute to the need for a more robust
synchronization solution. We denote the time over which synchronization is
maintained as $T_{b}$ (mnemonic batch), i.e., the time over which the error in
$\Delta\ll\tau_{A}$

Clock synchronization is sometimes achieved by directly sending Alice’s clock
signal to Bob over a separate channel via an optical link or using a radio-
frequency signal [7, 8, 9, 10, 11, 12, 13, 14, 15, 16]. However, this
introduces additional hardware requirements and increases the cost and
complexity of the setup. One way to avoid these additional resource
requirements is to use the quantum channel itself to transmit the information
necessary to perform the synchronization [17, 18, 19, 20]. One such qubit-
based synchronization protocol was introduced and demonstrated by Calderaro et
al. [17]. Their protocol uses a dedicated clock-synchronization phase followed
by a key distribution phase. In the synchronization phase, a pre-agreed
synchronization string is transmitted to Bob and the clocks are aligned during
post-processing.

Their procedure does not correct for clock frequency drift: It only addresses
the initial session time offset and frequency difference. If the clock
frequencies are not consistent, this method only temporarily aligns until the
clock drift becomes of-the-order-of the communication protocol temporal bin
width $\tau_{A}$. Correcting for clock frequency drift requires repeated
synchronization/key distribution phases with a regularity that depends on the
stability of the clocks used in the experiment. This reduces the overall
secure key rate because no QKD states can be sent while the synchronization
states are being sent, which may result in zero key rate due to finite-key
effects [21, 22].

Our method avoids these limitations by synchronizing the clocks using only
information that is already publicly sent over the insecure classical channel
by Alice and Bob for sifting and security analysis: The basis choices and the
mean photon number of the transmitted signal. Because we are transmitting only
one state in the monitoring basis, the basis choices provide information about
which of Bob’s measurement outcomes are more likely. The decoy state choices,
which determine Alice’s mean photon number for each wavepacket, also contain
information about Bob’s measurement outcomes. For example, Bob is unlikely to
record any detections if Alice sends the vacuum decoy state.

By comparing this information to his measurement outcomes, Bob can
probabilistically determine the timing offset. To account for potential clock
drift, Bob can perform this synchronization in batches of length $T_{b}$.
Thus, Bob can find the up-to-date timing offset and ensure that the basis
choices he publishes are properly lined up with the ones sent to him by Alice,
but this requires an efficient analysis method to reduce the data
requirements. Of course, our approach as well as Calderaro’s requires low
enough channel loss so that there are enough events received by Bob over a
drift interval as discussed below.

Another example of a qubit-based synchronization protocol for a continuously-
pumped entanglement-based QKD systems was introduced by Ho et al. [20]. Here,
they correlate Alice and Bob’s detection events without considering basis
information. Their synchronization method relies on Alice’s knowledge that
some communication time bins are empty (assuming essentially unit detection
efficiency for Alice’s setup) and hence Bob’s corresponding time bin should
also be empty. There is a single dominant peak in the correlation function
that identifies $\Delta$ assuming a large enough number of Bob’s detection
events. Because the detection timing information must already be shared
publicly, this strategy does not sacrifice any secure key. This method fails
when the probability of Alice generating a photon per communication time bin
approaches unity because every time bin is likely to be filled and hence the
correlation function will have multiple high-value peaks that creates timing
ambiguity.

In the next section, we outline our synchronization algorithm and its
advantages, and derive a formula for the synchronization probability using
Bayesian analysis. In Sec. 3 introduce a model system, and in Sec. 4 we
simulate data in this model system to demonstrate the effectiveness of our
method. In Sec. 5 we present our conclusions and the potential applicability
of this work to other QKD systems.

##  II Qubit-Based Synchronization Algorithm

Similar to previous approaches, our algorithm uses a cross-correlation of
Alice’s periodically transmitted data and Bob’s received data to find the
number of each type of event pairing, where the cross-correlation is computed
efficiently using a Fast Fourier Transform (FFT). One complication of a
prepare-and-measure scheme is that Alice attempts to send a quantum state
every communication time bin, corresponding to the high-photon-probability
limit of the Ho et al. [20] method discussed above. This problem is addressed
here using the decoy-state protocol [3], which must be used anyway to prevent
a photon-number-splitting attack.

Decoy states are sent by Alice randomly and correspond to wavepackets with a
mean photon number smaller than the signal state and often includes sending
the vacuum state. The vacuum state is particularly effective in the
synchronization process because Alice has high certainty that she sent no
photons, limited by her ability to completely block the source. Bob should
then also see no photons, limited by the source of detection clicks from non-
ideal effects such as detector dark counts, detector afterpulsing, stray
light, and the bleed through of light from Alice’s source.

Beyond the decoy states, there are additional sources of correlation that can
be exploited to help improve the synchronization process. For example, Alice’s
use of the efficient three-state protocol, where she only sends one state in
the monitoring basis, gives useful information if Alice and Bob also share
basis-state information, which is already required for sifting. We use a
Bayesian statistical method, described below, that uses all prior knowledge of
the system characteristics, such as the state fidelities, the mean photon
numbers, the channel loss, the fractional sorting of Bob’s device for the two
bases, and the detector efficiency, we generate a lookup table of Bob’s
detection probabilities for Alice’s different inputs. With these, we can
easily compute the synchronization probabilities of different possible offsets
using Bayesian statistics. Alice and Bob’s data is most correlated when they
are synchronized.

A significant advantage of our approach is that it does not sacrifice any
secure key: We only use the information that is already sent publically over
the insecure classical channel. This is an improvement over synchronization
protocols that share some fraction of the raw data for synchronization
purposes, as well as protocols that have a dedicated clock-synchronization
phase [17] during which no QKD states can be sent.

Bayesian analysis is a logical choice for synthesizing all available
information and using it to make accurate predictions about $\Delta$. It also
has the advantage that it predicts the probability that $\hat{\Delta}$ is the
best estimate of synchronization offset. This allows us to quantitatively
express our level of confidence in the synchronization estimate. Furthermore,
the additional information we incorporate in the protocol allows us to make a
decision with fewer received qubits, which makes the system more robust to
clock drift.

###  II.1 Synchronization Probability

Here we will use the strings of Alice and Bob’s data. A string of Bob’s data
consists of the results of each of his detectors at each sampling bin.
Typically, Bob’s strings are very sparse because there are many sampling bins
in which he registers no detections. A string of Alice’s data consists of her
published information at each sampling bin. If the communication time bin
width is greater than the sampling time bin width, Alice will have multiple
string entries for each state she sends, each corresponding to what she is
sending at that part of her duty cycle. Determining the synchronization
probability consists of comparing different strings of Bob’s data (starting at
different temporal offsets) to strings of Alice’s data and calculating which
of Bob’s strings $D$ is most likely to be the one generated by Alice’s
corresponding string. We determine, for a particular string of Bob’s, the
probability that it could have been generated by Alice’s published string.

Mathematically, we phrase this as the likelihood $p(D|S)$ of generating Bob’s
string $D$ given the assumption that its generating string is the one Alice
has published, denoted by $S$. The uninformed assumption, which we will denote
as $\bar{S}$, is that Bob’s string $D$ has been generated by a random string
other than Alice’s published string (from some other portion of Alice’s sent
data), with the stipulation that the other string is also periodic. This
mathematical framework will consider a subset of Alice’s data of $N$ sampling
bin widths compared against a subset of Bob’s data of $N+M$ sampling bin
widths, meaning there will be $M$ possible offsets to consider.

To begin in our protocol formalism, we note that $D$ is a string of length
$M+N$ of Bob’s measurements at each sampling bin (including sampling bins
where no detections were received). Each measurement $B_{i}$ in Bob’s string
consists of the click or no-click results at all of Bob’s detectors. Bob’s
string $D$ can be written as

$D=\\{B_{1},...,B_{M+N}\\},$ (2)

which we can rewrite as

$D=\\{B_{1},D^{\prime}\\},$ (3)

where

$D^{\prime}=\\{B_{2},...,B_{M+N}\\}.$ (4)

We prefer to write the likelihood $p(D|S)$ in terms of known quantities such
as the $p(B_{1}|S)$, the conditional probability of a time bin measurement
$B_{1}$ given $S$. Using this notation, $p(D|S)$ is given by

$p(D|S)=p(B_{1},D^{\prime}|S)=p(B_{1}|D^{\prime},S)p(D^{\prime}|S),$ (5)

where the final equality is a result of the product rule. Because we have
assumed that $B_{1}$ is generated from Alice’s string, knowing $D^{\prime}$
gives us no additional information about $B_{1}$. At best, it informs us
whether $S$ true, which is already assumed; the bits are otherwise independent
because Alice’s sequence is random. Using these observations, we obtain

$p(B_{1}|D^{\prime},S)=p(B_{1}|S),$ (6)

and, by extension,

$p(D|S)=\prod\limits_{i=1}^{N+M}p(B_{i}|S),$ (7)

allowing us to write the likelihood as the product of the measurement
probabilities at each sampling bin. We note that even in the example where
Alice only sends one state in the monitoring basis, Bob must still measure
both states in each basis to detect potential eavesdropper attacks [6, 5]. For
computational ease, we also determine each sampling bin measurement
probability as the product of the probabilities of the outcomes at the four
different detectors $b_{\ell}$, which are given by

$p(B_{i}|S)=\prod\limits_{\ell=1}^{4}p(b_{\ell}|S)$ (8)

Again, because the detector events are assumed to be generated by independent
random processes, these probabilities can be considered independent when the
generating string is known.

When the generating string is not known (under the uninformed assumption
$\bar{S}$), the detection probabilities can be approximated as independent
when the received mean photon number is low. Because the synchronization task
is most difficult in low-signal regimes, we use this approximation going
forward. Thus,

$p(D|\bar{S})=\prod\limits_{i=1}^{N+M}p(B_{i}|\bar{S})$ (9)

and

$p(B_{i}|\bar{S})=\prod\limits_{\ell=1}^{4}p(b_{\ell}|\bar{S}).$ (10)

For a given input from Alice, each of Bob’s four detectors has an opportunity
to detect a photon above the detection clicks arising from non-ideal
behaviors. Naturally, we will use our knowledge of the system (the state
fidelities, the quality of the polarization sorting, the dark count rates, the
detector efficiencies, and the signal and decoy received mean photon number)
to estimate the detection probabilities as accurately and efficiently as
possible. Using a lookup table of the detection probabilities for the
different inputs from Alice, these likelihoods can be calculated using
standard statistical methods.

However, the likelihood of generating $D$ from Alice’s published string is not
the same as the probability that Alice’s published string is the one that
generated $D$, which is given by $p(S|D)$ and is the most relevant quantity to
determine synchronization. Bayes’ theorem allows us to rewrite this quantity,
called the posterior, as

$p(S|D)=\frac{p(D|S)p(S)}{p(D)}.$ (11)

In addition, we must also include the information that we expect exactly one
correct synchronization offset (not just one on average).

To formulate the problem as an exclusive synchronization, we must find the
probability that some discreet timing offset, given by the time-bin index $j$,
is the correct synchronization offset, and that all the other offsets are
incorrect. In other words, the probability that, for a given string of length
$N$ published by Alice, all the measurements before the $j^{th}$ bin are
generated randomly, the measurements from $j$ to $j+N$ are generated from
Alice’s published string, and the measurements after $j+N$ are generated
randomly. Under these assumptions, we can write $p(B_{1},...,B_{M+N}|S_{j})$
as a product of the likelihoods of these three sections as

$p(B_{1},...,B_{M+N}|S_{j})=p(B_{1},...,B_{j-1}|\bar{S_{j}})p(B_{j},...,B_{j+N}|S_{j})p(B_{j+N+1},...,B_{M+N}|\bar{S_{j}}).$
(12)

Here we introduce $\bar{S_{j}}$, the assumption that the data is produced by a
random string other than the synchronization string in question, but one with
the same phase (i.e., the signal arrives at the same time bin in each period
as it does for $S_{j}$).

We can find the conditional probability for matching Alice’s string to Bob’s
string at a potential synchronization index $j$ in this framework using Eq.
11, which gives

$p(S_{j}|B_{1},...,B_{M+N})=\dfrac{p(B_{1},...,B_{M+N}|S_{j})p(S_{j})}{p(B_{1},...,B_{M+N})}.$
(13)

Equation 13 is our main result and is the quantity of interest to identify
clock synchronization between Alice and Bob. We determine the optimum
synchronization index based on the value of $j$ that maximizes this quantity,
and the quantity itself gives us our confidence in that choice.

The denominator in Eq. 13 can be written in terms of known quantities using
marginalization. Marginalization consists of rewriting a probability as a sum
of the comprehensive conditional probabilities; in this case, the different
possible synchronization indices written as

$p(S_{j}|B_{1},...,B_{M+N})=\dfrac{p(B_{1},...,B_{M+N}|S_{j})p(S_{j})}{\displaystyle\sum_{i=1}^{M}p(B_{1},...,B_{M+N}|S_{i})p(S_{i})},$
(14)

where the $i$ denotes the other potential synchronization indices.

To evaluate Eq. 13, we the likelihoods $p(B_{1},...,B_{M+N}|S_{j})$ and
$p(B_{1},...,B_{M+N}|S_{i})$ can be determined using Eqs. 7, 9 and, 12. The
quantity $p(S_{j})$, called the prior, is the ad hoc probability that $D$
corresponds to Alice’s published string. That is, that we are at the correct
synchronization index. We use a uniform prior, which assumes each candidate
has a naïve $1/M$ probability of being the correct one given that we have $M$
candidate indices, which means that

$p(S_{i})=p(S_{j})=\dfrac{1}{M}$ (15)

so that the prior terms cancel, giving us

$p(S_{j}|B_{1},...,B_{M+N})=\dfrac{p(B_{1},...,B_{M+N}|S_{j})}{\displaystyle\sum_{i=1}^{M}p(B_{1},...,B_{M+N}|S_{i})}.$
(16)

Next, we apply Eq. 12 to obtain

$\displaystyle p(S_{j}|B_{1},...,B_{M+N})=$
$\displaystyle\dfrac{p(B_{1},...,B_{j-1}|\bar{S_{j}})p(B_{j},...,B_{j+N}|S_{j})p(B_{j+N+1},...,B_{M+N}|\bar{S_{j}})}{\displaystyle\sum_{i=1}^{M}p(B_{1},...,B_{i-1}|\bar{S_{i}})p(B_{i},...,B_{i+N}|S_{i})p(B_{i+N+1},...,B_{M+N}|\bar{S_{i}})}$

and use Eqs. 7 and 9 (of which the latter uses a low received mean photon
number approximation) to write everything in terms of known quantities as

$p(S_{j}|B_{1},...,B_{M+N})\approx\dfrac{\displaystyle\prod_{k=1}^{j-1}p(B_{k}|\bar{S_{j}})\displaystyle\prod_{k=j}^{j+N}p(B_{k}|S_{j})\displaystyle\prod_{k=j+N+1}^{M+N}p(B_{k}|\bar{S_{j}})}{\displaystyle\sum_{i=1}^{M}\Bigg{(}\displaystyle\prod_{k=1}^{i-1}p(B_{k}|\bar{S_{i}})\displaystyle\prod_{k=i}^{i+N}p(B_{k}|S_{i})\displaystyle\prod_{k=i+N+1}^{M+N}p(B_{k}|\bar{S_{i}})\Bigg{)}}$
(18)

Equation 18 is our master equation for the synchronization probability of an
index $j$. The numerator consists of the probability of an $N$-length string
of Bob’s data starting at $j$ being produced by Alice’s published string,
along with the probability that the remaining data was produced by an unknown
string of Alice’s data. The denominator sums this same quantity over all
possible synchronization indices, ensuring normalization. We take the value of
$j$ that maximizes this quantity to be the optimum synchronization index, and
the value of $p(S_{j}|B_{1},...,B_{M+N})$ gives us the probability that we are
correct. We can compute this conditional probability using FFTs to count the
number of each unique bin measurement along with a lookup table of the
probabilities of the events.

##  III Model System

To illustrate our protocol, we simulate a model QKD system using a
polarization-based prepare-and-measure protocol with decoy states and only
sending one state in the monitoring basis. We set Alice’s repetition rate to
be $f_{A}=1/\tau_{A}$ and a wavepacket duration of $\Delta t=\tau_{A}/m$ with
$m=8$ for a duty cycle of 12.5 percent. We set Bob’s sampling rate to $nf_{A}$
with $n=8$ so that his sample period is matched to the wavepacket duration.
These conditions are illustrated in Fig. 1. Alice generates a pseudorandom
sequence such that four quantum states L/R/H and a vacuum decoy state (a decoy
state with mean photon number equal to zero) are sent in equal parts on
average.

Figure 1: Illustration of the relative times used in the QKD protocol. Here,
the signal (red) straddles bins 1-2 due to an offset of $\Delta$, and we do
not consider bins 3-8. We take $\tau_{A}=\tau_{B}$, which is approximately
correct for a short enough data subset.

For our numerical experiments, we simulate a QKD session by generating data
that emulates the state preparation and measurement, including aspects such as
the received mean photon number $\mu$, probability of a detector dark count
$d$ over one communication bin width $\tau_{A}$, and variation in $\Delta$ due
to clock drift, assumed to be constant over $T_{b}$. This allowed us to test
how these factors impact the synchronization performance. We assume a
transmitted mean photon number $\mu_{A}=1$ where the received mean photon
number $\mu=\eta\mu_{A}$ for a channel transmission $\eta$. While this
$\mu_{A}$ is on the upper end of values used in typical experiments, it allows
us to explore the performance and limitations of our algorithm at or beyond
the greatest received mean photon number one would realistically use:
$\mu_{A}=1$ with zero loss.

Assuming a Poisson distribution for Alice’s source, the probability of Bob
registering a click $p(click)$ over a period $\tau_{A}$ at a particular
detector $\ell$ is given by

$p(click,\ell)=1-(1-d)e^{\mu_{\ell}}$ (19)

where $\mu_{\ell}$ is the mean photon number received by detector $\ell$. The
portion of the total mean photon number $\mu$ that goes to the different
detectors depends on which polarization state is sent. We use ideal BB84
sorting in our model system so that all states have an equal chance of being
measured in either basis. States measured in the same basis as they are
prepared are detected accurately, while states measured in the opposite basis
have an equal chance of being measured in either opposite-basis state. For
example, if Alice prepared an H-state that Bob receives $\mu=0.8$, Bob’s
measures $\mu_{H}=0.4$, $\mu_{v}=0$, and $\mu_{L}=\mu_{R}=0.2$.- In the
low-$\mu$ limit, Eq. 19 can be approximated as

We assume that the observation window is long enough so that the $p$’s and
$\mu$’s can be estimated accurately from the finite number of observations.
This means the average click probability can be extracted from the Bob’s raw
data and we rewrite Eq. 19 as a function of ${p(click,\ell)}$ so that

${\mu_{\ell}}=ln\bigg{(}\dfrac{1-d}{1-{p(click,\ell)}}\bigg{)}$ (20)

and we estimate the received mean photon number of a signal state as

${\mu}=\dfrac{4}{3}\displaystyle\sum_{\ell=1}^{4}ln\bigg{(}\dfrac{1-d}{1-{p(click,\ell)}}\bigg{)},$
(21)

which just sums the average mean photon number of the different detectors and
multiplies by a factor of 4/3 to account for the fact that we are sending
vacuum states 25% of the time.

We divide the data set into subsets duration $T_{b}$ and perform
synchronization and sifting on each subset. Bob can record up to 8 events
(each of which may or may not include a detection event or dark count)
assuming that the detector deadtime is less than Bob’s sampling time. However,
because the clocks can only be synchronized to a resolution of Bob’s sampling
bin width, we expect Alice’s wavepacket to straddle 2 bins as illustrated in
Fig. 1, with the end bins only having a partial wavepacket. The remaining 6
bins only contain dark counts, which can be discarded after we determine
$\Delta$ to reduce noise. This amounts to detector time-gating in the post-
analysis.

We assume that Bob begins recording before Alice begins transmitting, and
continues to record after she stops sending, so our received data is bookended
by low signal regions. We find a best-fit step function to identify where the
transmission begins and ends, which gives us a coarse approximation of the
synchronization index. For a range of different string lengths $N$ that
determine the number of sampling bin widths in each synchronization subset, we
examine a window of $M=4,000$ nearby potential synchronization indices. This
value is chosen based on the typical precision of the coarse approximation of
the synchronization given by the best-fit step function.

##  IV Synchronization Simulations

To verify that our algorithm returns an accurate probability of
synchronization, we run 1,000 simulated trials with a known synchronization
index and compared the average calculated probability of synchronization
$p(S_{j}|B_{1},...,B_{M+N})$ to the average rate of finding the correct index,
which we denote by $f(S_{j}|B_{1},...,B_{M+N})$, in Fig. 2. If our model is
accurate, then $p(S_{j}|B_{1},...,B_{M+N})\sim f(S_{j}|B_{1},...,B_{M+N})$, in
which case we can take $p(S_{j}|B_{1},...,B_{M+N})$ to be a reliable metric
for quantifying our confidence in obtaining the correct $\Delta$.

Figure 2:  Bob’s required data record length needed to determine
synchronization for two different channel transmissions of (a) $\eta=0.05$,
corresponding to $\mu=0.05$ and (b) $\eta=1$, corresponding to $\mu=1$. We
also show the probability of not obtaining synchronization, which better
highlights transition to high-certainty synchronization.

We see that $p(S_{j}|B_{1},...,B_{M+N})\sim f(S_{j}|B_{1},...,B_{M+N})$ to
within our errorbars for moderate channel loss (Fig. 2a). However,
$p(S_{j}|B_{1},...,B_{M+N})$ is consistently larger than
$f(S_{j}|B_{1},...,B_{M+N})$ for the case of zero channel loss (Fig. 2b), a
condition that is unlikely to be encountered in an experiment but highlights
the limitation of our algorithm. This result is not surprising given that our
derivation given in Sec. II assumes low $\mu$ to arrive at Eq. 9. Assuming a
transmitted mean photon number of 1, Fig. 2 (b) corresponds to a zero channel
loss system. This represents an upper limit on $\mu$ encountered in a typical
decoy state protocol where $\mu_{A}\lesssim 1$ and thus, also serves as a
lower bound on the accuracy of our calculated synchronization probability.

A lower received mean photon number means a lower density of detected events.
Because detected events provide more information than no-detection events, a
lower $\mu$ requires us to consider a larger set of sampling bin widths $N$ to
achieve the same synchronization confidence. Despite the fact that
$p(S_{j}|B_{1},...,B_{M+N})$ does not match $f(S_{j}|B_{1},...,B_{M+N})$ as
well at higher values of $\mu$, we can still achieve equivalent average values
of $f(S_{j}|B_{1},...,B_{M+N})$ at lower values of $N$. This fact is also
illustrated in Fig. 3, where we see a direct correlation between $\mu$ and $N$
at which the synchronization probabilities converge to one: The higher values
of $\mu$ converge at lower values of $N$.

Figure 3:  Average calculated synchronization probability as a function of
string length on a logarithmic scale for different received mean photon
numbers. The probability of registering a dark count during one communication
bin width is $d=8\times 10^{-4}$.

Another way to view this relation between $\mu$, $N$, and
$p(S_{j}|B_{1},...,B_{M+N})$ is to consider the string length $N$ required to
achieve a particular synchronization confidence as a function of $\mu$ as
shown in Fig. 4. For high $\mu$ and low $N$, we observe an approximately
linear relation between $log_{10}\mu$ and $log_{10}N$ with a slope of $\sim$
-1, which means that $N~{}1/\mu$. For lower $\mu$, where there are fewer
events and dark counts play a larger role, the probability curves exhibit
steeper slopes, demonstrating that synchronization becomes increasingly
difficult. This data can be used to estimate whether it is possible to
synchronize over an experimentally measured temporal block length $T_{b}$ and,
if it is possible, how low a value of $\mu$ can be tolerated while still
synchronizing reliably. As a concrete example, Bob needs 33,110 sampling bin
widths, or about 4,140 communication bin widths, to achieve a 95% confidence
for clock synchronization for $\mu=0.01$ and $d=8\times 10^{-4}$. This means
we can tolerate clock drifts approaching 1 part in 4,140 because our method
assumes that the clock drift is much less than one communication bin width.

Figure 4:  Dependence of string length threshold to achieve 95 percent
synchronization confidence on received mean photon number on a logarithmic
scale, parameterized by different dark count probabilities.

##  V Conclusions

In conclusion, we develop a novel probabilistic approach to qubit-based clock
synchronization using Bayesian analysis. By exploiting correlations between
information Alice shares publicly, such as basis and decoy state choices, and
Bob’s detection events, we can find the correct synchronization clock offset
without sacrificing any secret key. Additionally, our algorithm is more robust
to noise, loss, and clock drift in comparison to other protocols by
incorporating all publicly available information using the Bayesian framework.
Finally, we demonstrate that our algorithm is successful and robust using a
simulated BB84 communication scheme, which confirms that our synchronization
metric corresponds to the probability of synchronization, especially in the
low-$\mu$ limit. Our algorithm is applicable to other QKD systems that use
other degrees-of-freedom of the photon for which it is possible to divulge
some timing information.

## Acknowledgements

This material is based on research sponsored by NASA under grant 80NSSC20K0629
and the Air Force Research Laboratory and the Southwestern Council for Higher
Education under agreement FA8650-19-2-9300. The U.S. Government is authorized
to reproduce and distribute reprints for Governmental purposes notwithstanding
any copyright notation thereon. The views and conclusions contained herein are
those of the authors and should not be interpreted as necessarily representing
the official policies or endorsements, either expressed or implied, of NASA,
the Southwestern Council for Higher Education and the Air Force Research
Laboratory (AFRL), or the U.S. Government. R.D.C. acknowledge discussions of
the Bayesian analysis with Richard Furnstahl. All code and data used in
simulations is publicly available on GitHub:
https://github.com/roderickdcochran/qubit_based_synchronization

## References

  * Bennett and Brassard [2014] C. H. Bennett and G. Brassard, Quantum cryptography: Public key distribution and coin tossing, Theor. Comput. Sci. 560, 7 (2014).
  * Ekert [1991] A. Ekert, Quantum cryptography based on bell theorem, Phys. Rev. Lett. 67, 661 (1991).
  * Lo  _et al._ [2005] H.-K. Lo, X. Ma, and K. Chen, Decoy state quantum key distribution, Phys. Rev. Lett. 94, 230504 (2005).
  * Bennett  _et al._ [1992] C. H. Bennett, F. Bessette, G. Brassard, L. Salvail, and J. Smolin, Experimental quantum cryptography, J. Cryptology 5, 3 (1992).
  * Islam  _et al._ [2018] N. T. Islam, C. C. W. Lim, C. Cahall, J. Kim, and D. J. Gauthier, Securing quantum key distribution systems using fewer states, Phys. Rev. A 97, 042347 (2018).
  * Tamaki  _et al._ [2014] K. Tamaki, M. Curty, G. Kato, H.-K. Lo, and K. Azuma, Loss-tolerant quantum cryptography with imperfect sources, Phys. Rev. A 90, 052314 (2014).
  * D’Auria  _et al._ [2020] V. D’Auria, B. Fedrici, L. A. Ngah, and et al., A universal, plug-and-play synchronisation scheme for practical quantum networks, npj Quantum Inf 6, https://doi.org/10.1038/s41534-020-0245-9 (2020).
  * Korzh  _et al._ [2015] 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, Nat. Photonics 9, 163 (2015).
  * Liu  _et al._ [2010] Y. Liu, T.-Y. Chen, J. Wang, W.-Q. Cai, X. Wan, L.-K. Chen, J.-H. Wang, S.-B. Liu, H. Liang, L. Yang, C.-Z. Peng, K. Chen, Z.-B. Chen, and J.-W. Pan, Decoy-state quantum key distribution with polarized photons over 200 km, Opt. Express 18, 8587 (2010).
  * Liu and Yin [2019] P. Liu and H.-L. Yin, Secure and efficient synchronization scheme for quantum key distribution, OSA Continuum 2, 2883 (2019).
  * Walenta  _et al._ [2014] N. Walenta, A. Burg, D. Caselunghe, J. Constantin, N. Gisin, O. Guinnard, R. Houlmann, P. Junod, B. Korzh, N. Kulesza, M. Legré, C. W. Lim, T. Lunghi, L. Monat, C. Portmann, M. Soucarros, R. T. Thew, P. Trinkler, G. Trolliet, F. Vannel, and H. Zbinden, A fast and versatile quantum key distribution system with hardware key distillation and wavelength multiplexing, New J. Phys. 16, 013047 (2014).
  * Dynes  _et al._ [2016] J. Dynes, W. Tam, A. Plews, and et al, Ultra-high bandwidth quantum secured data transmission, Sci Rep 6, 35149 (2016).
  * Sasaki  _et al._ [2011] M. Sasaki, M. Fujiwara, H. Ishizuka, W. Klaus, K. Wakui, M. Takeoka, S. Miki, T. Yamashita, Z. Wang, A. Tanaka, K. Yoshino, Y. Nambu, S. Takahashi, A. Tajima, A. Tomita, T. Domeki, T. Hasegawa, Y. Sakai, H. Kobayashi, T. Asai, K. Shimizu, T. Tokura, T. Tsurumaru, M. Matsui, T. Honjo, K. Tamaki, H. Takesue, Y. Tokura, J. F. Dynes, A. R. Dixon, A. W. Sharpe, Z. L. Yuan, A. J. Shields, S. Uchikoga, M. Legré, S. Robyr, P. Trinkler, L. Monat, J.-B. Page, G. Ribordy, A. Poppe, A. Allacher, O. Maurhart, T. Länger, M. Peev, and A. Zeilinger, Field test of quantum key distribution in the tokyo qkd network, Opt. Express 19, 10387 (2011).
  * Wang  _et al._ [2014] S. Wang, W. Chen, Z.-Q. Yin, H.-W. Li, D.-Y. He, Y.-H. Li, Z. Zhou, X.-T. Song, F.-Y. Li, D. Wang, H. Chen, Y.-G. Han, J.-Z. Huang, J.-F. Guo, P.-L. Hao, M. Li, C.-M. Zhang, D. Liu, W.-Y. Liang, C.-H. Miao, P. Wu, G.-C. Guo, and Z.-F. Han, Field and long-term demonstration of a wide area quantum key distribution network, Opt. Express 22, 21739 (2014).
  * Vallone  _et al._ [2015] G. Vallone, D. G. Marangon, M. Canale, I. Savorgnan, D. Bacco, M. Barbieri, S. Calimani, C. Barbieri, N. Laurenti, and P. Villoresi, Adaptive real time selection for quantum key distribution in lossy and turbulent free-space channels, Phys. Rev. A 91, 042320 (2015).
  * Bourgoin  _et al._ [2015] J.-P. Bourgoin, N. Gigov, B. L. Higgins, Z. Yan, E. Meyer-Scott, A. K. Khandani, N. Lütkenhaus, and T. Jennewein, Experimental quantum key distribution with simulated ground-to-satellite photon losses and processing limitations, Phys. Rev. A 92, 052339 (2015).
  * Calderaro  _et al._ [2020] L. Calderaro, A. Stanco, C. Agnesi, M. Avesani, D. Dequal, P. Villoresi, and G. Vallone, Fast and simple qubit-based synchronization for quantum key distribution, Phys. Rev. Applied 13, 054041 (2020).
  * Agnesi  _et al._ [2020] C. Agnesi, M. Avesani, L. Calderaro, A. Stanco, G. Foletto, M. Zahidy, A. Scriminich, F. Vedovato, G. Vallone, and P. Villoresi, Simple quantum key distribution with qubit-based synchronization and a self-compensating polarization encoder, Optica 7, 284 (2020).
  * Avesani  _et al._ [2021] M. Avesani, L. Calderaro, G. Foletto, C. Agnesi, F. Picciariello, F. B. L. Santagiustina, A. Scriminich, A. Stanco, F. Vedovato, M. Zahidy, G. Vallone, and P. Villoresi, Resource-effective quantum key distribution: a field trial in padua city center, Opt. Lett. 46, 2848 (2021).
  * Ho  _et al._ [2009] C. Ho, A. Lamas-Linares, and C. Kurtsiefer, Clock synchronization by remote detection of correlated photon pairs, New J. Phys. 11, 045011 (2009).
  * Hayashi [2007] M. Hayashi, Upper bounds of eavesdropper’s performances in finite-length code with the decoy method, Phys. Rev. A 76, 012329 (2007).
  * Lim  _et al._ [2014] C. C. W. Lim, M. Curty, N. Walenta, F. Xu, and H. Zbinden, Concise security bounds for practical decoy-state quantum key distribution, Phys. Rev. A 89, 022307 (2014).