# Qubit-Based Clock Synchronization for QKD Systems Using a Bayesian Approach
## 2 Qubit-Based Synchronization Algorithm  
Similar to previous approaches, our algorithm uses a cross-correlation of [PERSON]'s periodically transmitted data and [PERSON]'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 [PERSON] attempts to send a quantum state every communication time bin, corresponding to the high-photon-probability limit of the [PERSON] 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 [PERSON] 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 [PERSON] has high certainty that she sent no photons, limited by her ability to completely block the source. [PERSON] 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 [PERSON]'s source.  
Beyond the decoy states, there are additional sources of correlation that can be exploited to help improve the synchronization process. For example, [PERSON]'s use of the efficient three-state protocol, where she only sends one state in the monitoring basis, gives useful information if [PERSON] and [PERSON] 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 [PERSON]'s device for the two bases, and the detector efficiency, to generate a lookup table of [PERSON]'s detection probabilities for [PERSON]'s different inputs. With these, we can easily compute the synchronization probabilities of different possible offsets using Bayesian statistics. [PERSON] and [PERSON]'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 publicly 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.  
Our algorithm uses FFTs to compute cross-correlations between [PERSON]'s inputs and [PERSON]'s outputs, allowing us to count the number of each type of input-output pairing for the different time offsets. The computational complexity of our algorithm is dominated by these FFTs, which go as \(\mathcal{O}(N\log N)\) where \(N\) is the number of sampling bins. Each cross-correlation requires three FFT computations, so the number of FFTs that must be performed is \(3\times n_{in}\times n_{out}\) for a number of distinct inputs \(n_{in}\) and distinct outputs \(n_{out}\). In this example, \(n_{in}=5\) (H/V signal, H/V decoy, L/R signal, L/R decoy, and vacuum) and \(n_{out}=4\) (H,V,L, and R), thus maintaining the computational complexity of \(\mathcal{O}(N\log_{2}N)\).