Quantum Complementarity Approach to Device-Independent Security

Xingjian Zhang^1
Pei Zeng^1
Tian Ye^1
Hoi-Kwong Lo^2, 3, 4
Xiongfeng Ma^1

$^1$Center for Quantum Information, Institute for Interdisciplinary Information Sciences, Tsinghua University, Beijing 100084, China
$^2$Department of Physics, University of Hong Kong, Pokfulam, Hong Kong
$^3$Centre for Quantum Information and Quantum Control (CQIQC), Dept. of Electrical & Computer Engineering and Department of Physics, University of Toronto, Toronto, Ontario, M5S 3G4, Canada
$^4$Quantum Bridge Technologies, Inc., 100 College Street, Toronto, ON M5G 1L5, Canada

Complementarity is an essential feature of quantum mechanics. The preparation of an eigenstate of one observable implies complete randomness in its complementary observable. In quantum cryptography, complementarity allows us to formulate security analyses in terms of phase-error correction. However, in the device-independent regime that offers security without device characterization, the concept becomes much subtler. Security proofs of device-independent quantum cryptography tasks are often complex and quite different from those of their more standard device-dependent cousins. The existing proofs pose huge challenges to experiments, among which large data-size requirement is a crux. Here, we show the complementarity security origin of the device-independent tasks. By linking complementarity with quantum nonlocality, we recast the device-independent scheme into a quantum error correction protocol. Going beyond the identical-and-independent-distribution case, we consider the most general attack. We generalize the sample entropy in classical Shannon theory for the finite-size analysis. Our method exhibits good finite-size performance and brings the device-independent scheme to a more practical regime. Applying it to the data in a recent ion-trap-based device-independent quantum key distribution experiment, one could reduce the requirement on data size to less than a third. Furthermore, the complementarity approach can be naturally extended to advantage key distillation to ease experiments by tolerating higher loss and lower transmittance.

Introduction. —As demonstrated by Heisenberg, complementary observables, such as position and momentum, where the full knowledge of one property implies the ignorance of the other, exist [Heisenberg, 1927]. The inability to measure multiple observables simultaneously indicates a fundamental limitation of learning physical properties, thus violating the tenet of determinism in Newtonian physics. In the quest to understand quantum physics, complementarity is found to be closely related to the nonlocal physical state — entanglement [Einstein et al., 1935]. As the strongest method to verify its existence, the Bell test has drawn considerable attention [Bell, 1964]. In the famous Clauser-Horne-Shimony-Holt (CHSH) Bell test, space-like separated parties, Alice and Bob, each have a black box for random measurements. Without any communication, Alice and Bob each send a random input $X,Y\in\{0,1\}$ to their own devices, which then output a value $A,B\in\{+1,-1\}$, respectively. With respect to these random variables, the expected Bell value is given by the following expression [Clauser et al., 1969],

\begin{equation}\label{Eq:AveBellValue}
\begin{aligned}
S &= \sum_{x,y\in\{0,1\}}(-1)^{xy} \mathbb{E}(AB|X=x,Y=y),
\end{aligned}
\end{equation}

where the function $\mathbb{E}(\cdot)$ represents the expected value and lowercase letters represent the specific realizations of the associated random variables. Deterministic classical physics upper bounds the Bell value by $S\leq2$, but quantum physics allows for a higher value of $S$. Such a correlation, called Bell nonlocality, necessarily implies entanglement. In addition, to unveil the nonlocal correlation, the observables corresponding to the random inputs, $\hat{A}_0,\hat{A}_1$ on Alice's side and $\hat{B}_0,\hat{B}_1$ on Bob's side, must be non-commuting. Furthermore, the nonlocal correlation indicates the unpredictable randomness of the outputs. As the conclusions do not depend on any system characterization, the scenario enjoys a device-independent feature [Mayers and Yao, 1998, Acín et al., 2007].

Aside from fundamental interests, with recent progress in quantum information, complementarity and nonlocality have found novel applications. One of the most profound applications of complementary observables is quantum communication. In quantum key distribution (QKD), where two remote parties aim to obtain identical private keys, legitimate users can encode their information in the basis states of complementary observables at random [Bennett and Brassard, 1984, Ekert, 1991]. With the aid of measurement complementarity and quantum error correction, QKD security can be established [Lo and Chau, 1999, Shor and Preskill, 2000, Koashi, 2009]. The connection between quantum nonlocality and measurement complementarity allows us to go even further — giving rise to the device-independent quantum key distribution (DIQKD) [Mayers and Yao, 1998, Acín et al., 2007]. Legitimate users do not need to characterize their quantum devices to guarantee security. Instead, they take key generation rounds and Bell tests at random, where the Bell value provides a “self-test” of the devices in use. Quantum nonlocality solves the security loopholes caused by malfunctioning or imperfection of quantum devices in common device-dependent QKD protocols once and for all [Xu et al., 2020][Note, however, that DIQKD is still vulnerable to memory attacks and covert channels. A memory attack may occur when the devices are reused for multiple QKD sessions, where the untrusted devices may store the key information in one DIQKD session and leak it via the necessary public communication required by the protocol in new sessions [Barrett et al., 2013]. A covert channel signals the key information to the outside in an unnoticed way other than the public communication allowed by the protocol. We do not discuss these issues in this work. Particularly, there is no memory attack if we only consider one QKD session. For discussions on practical countermeasures, one may refer to Ref. [Curty and Lo, 2019]. Note that in a different QKD protocol, measurement-device-independent quantum key distribution (MDIQKD) [Lo et al., 2012, Braunstein and Pirandola, 2012], the problem of memory attacks and covert channels can be naturally avoided on the measurement site.].
With recent development in the theory of quantum entropies, a few analyses finally arrive at full device-independent security against the most general attacks [Vazirani and Vidick, 2014, Miller and Shi, 2016, Arnon-Friedman et al., 2018, Zhang et al., 2020].  On the experimental side, after decades of efforts, a complete loophole-free DIQKD experiment has been conducted for the first time with delicate implementation on an ion-trap platform [Nadlinger et al., 2022]. There is also progress in the photonic [Liu et al., 2022] and cold-atom [Zhang et al., 2022] platforms. These works mark a major breakthrough toward a future quantum internet.

Despite the development in both theories and experiments of DIQKD, the role of complementarity remains vague in device-independent security. Rather than being based on the intuitive thinking of uncertainty relation, which is common practice in the trusted-device scenarios [Koashi, 2009], the existing security analyses are often abstract in an operational interpretation and share a much different conceptual flavor. Some works attempt to unite the device-independent scenario to its device-dependent cousins. Overall, the target is characterizing the key privacy by the complementary observable to the key generation measurement and linking it with the Bell value. Yet the picture of this approach is incomplete. Early efforts fail in providing a tight relation between nonlocality and complementarity [Tsurumaru and Ichikawa, 2016]. While a recent work finally gives the desired link [Woodhead et al., 2021], the result does not go into the general adversarial statistics that are possibly not independent and identically distributed (i.i.d.), unless resorting to the existing methods of quantum entropic measures for a full DIQKD security analysis.

Security Analysis. —In this work, we present a simple security proof of sequential DIQKD against the most general attacks — coherent attacks — where the system behavior is not assumed to be i.i.d., and complete the analysis along the complementarity approach. We consider a variant of Ekert's entanglement-based QKD protocol [Ekert, 1991], which is similar to the CHSH test setting with an additional measurement on Alice's side [Acín et al., 2006]. The users first perform random quantum measurements, including key generation measurements, where $X=2,Y=0$, and Bell tests, where $X,Y\in\{0,1\}$. After accumulating a sufficient quantity of data, based on quantum bit error rate $e_b$ and observed average Bell value $\bar{S}$, the users perform information reconciliation and privacy amplification to process the key to be identical and private, respectively.

We analyze the final secure key length after one complete run of the entire protocol. Different from common QKD, as the quantum devices are now uncharacterized or even untrusted, the measurements may have a memory effect and hence history-dependent performance [Pironio et al., 2009]. To deal with this, we can depict an $n$-round experiment with a system evolution on $n$ subsystems for both parties, where the memory effect from previous events is equivalently embedded in the state preparation. We leave the detailed modeling in Appendix <ref>. Unlike the existing approaches based on entropic measures, we recast the DIQKD security analysis into quantum phase error correction [Lo and Chau, 1999, Koashi, 2009]. In this scenario, information reconciliation and privacy amplification can be decoupled. The former task is essentially a classical procedure and relatively easy to analyze. In $m$ key generation rounds, the number of reconciled key bits can be lower bounded by $I_{AB}\geq m[1-fh(e_b)]$, with $f\geq1$ an appropriate information reconciliation efficiency parameter. The essence of security analysis is to estimate the amount of information leakage in key generation, reflected in the cost of privacy amplification.

The complementarity approach starts with the intuitive idea of quantum uncertainty. The secrecy is cast in Eve's ignorance of the measurement outcomes of $\hat{B}_0$, which form the reconciled key. As shown in Fig. <ref>(a), to quantify the adversary's uncertainty on the user side, Alice and Bob explore the complementary basis. That is, given that Bob has measured the complementary observable of $\hat{B}_0$, how well can Alice guess the outcome? The higher the guessing probability is, the less key information is leaked outside. An incorrect guess in a single round is called a phase error and the joint measurement result is called a phase-error pattern. The cost for privacy amplification is given by the number of most likely phase-error patterns, which we term phase-error cardinality. Then, the target of privacy estimation is two-fold: define the quantum measurement that gives rise to phase errors and estimate the phase-error cardinality from observed statistics.

It is challenging to tackle multiple rounds in bulk and deal with non-i.i.d. statistics directly. Instead,  we start with a single round, where we define the phase error and determine its probability from the Bell value. Then, we relate probabilities with frequencies in the non-i.i.d. setting, as shown in Fig. <ref>(b). We aim at estimating key privacy in terms of the phase-error sample entropy through observed Bell test statistics.

(a) The basic idea of the complementarity approach.

(b) The flowchart of privacy estimation. The two upper boxes indicate single-round probabilities and the two lower boxes indicate statistics over multiple rounds.

We first focus on a single round. In the CHSH test, as there are only two measurement bases for each party and two outcomes for each measurement, one can apply Jordan's lemma and restrict the unknown quantum system to a low-dimensional Hilbert space [Pironio et al., 2009] (see Lemma <ref> in Appendix). Conditioned on previous events, Eve squashes the quantum system of Alice and Bob into a pair of qubits and prepares their possible measurements to be projective observables. With a qubit subspace, we can define the complementary observable of $\hat{B}_0$, denoted as $\hat{B}_0^\perp$. The eigenvectors of the two observables form mutually unbiased bases. In a virtual experiment, Alice optimizes an auxiliary measurement, $\hat{A}_{\theta}$, to maximize its correlation with $\hat{B}_0^\perp$ over the pair of qubits, $\langle\hat{A}_{\theta}\otimes\hat{B}_0^\perp\rangle$, or equivalently, to minimize the phase-error probability, $(1-{\langle\hat{A}_{\theta}\otimes\hat{B}_0^\perp\rangle})/2$. Though the users cannot actually access $\hat{A}_{\theta}$ and $\hat{B}_0^\perp$, the relation between nonlocal behavior and measurement complementarity creates a bridge. Intuitively, a larger Bell value implies a smaller phase-error probability and more uncertainty from Eve's perspective. Note that different implementations can lead to the same Bell value, among which we need to consider the worst case for the legitimate users. In the end, the phase-error probability can be upper-bounded by

\begin{equation}\label{eq:PhaseErrorProb}
\begin{split}
e_{p}(S)&\equiv\dfrac{1}{2}\left(1-\min_{\rho,\hat{A}_0,\hat{A}_1,\hat{B}_0,\hat{B}_1}\max_{\hat{A}_{\theta}}{\langle\hat{A}_{\theta}\otimes\hat{B}_0^\perp\rangle}\right) \\
\left\{
\begin{tabular}{ll}
$\dfrac{1-\sqrt{(S/2)^2-1}}{2}$, & $2<S\leq2\sqrt{2}$,\\
$\dfrac{1}{2}$, & $S\leq2$,
\end{tabular}
\right.
\end{split}
\end{equation}

where the pair of qubits, $\rho$, and the underlying Bell-test observables should give the expected Bell value, $S$. We leave its derivation in Appendix <ref>.

Next, we extend the results to the case of multiple rounds. Though the behavior of untrusted quantum devices may not be i.i.d. over the rounds under the most general attacks, fortunately, the sequential setting defines a time order for measurements. Hence, this process assures that the observables in each round depend only on the history but not the future. Furthermore, the correlations in both the quantum state and measurement devices from previous events are fully absorbed into the phase-error probability and the expected Bell value in each round. We can thus apply martingale analyses to their associate random variables. To guarantee that the martingale variables associated with the phase errors and Bell values share the same filtration, we also embed the random variables of measurement settings into the filtration. Then, the single-round relation between phase-error probability and expected Bell value bridges the martingales. In this way, we can estimate the phase-error cardinality in the key generation rounds from statistics in Bell-test rounds. Finally, we employ a modified version of Azuma's concentration inequality [Azuma, 1967], namely, Kato's inequality [Kato, 2020], to relate the probabilities of martingale variables with their corresponding frequencies.

Different from common complementarity-based QKD analyses, a difficult point here is that the phase-error rate, the average number of phase errors occurring in a round, is not a good measure of privacy. Note that Eve may set different expected Bell values over the rounds, while Alice and Bob can only estimate the average. Due to convexity issues, the relation between the phase-error probability and the Bell value in expectation does not imply a similar relation between the phase-error rate and the average Bell value over multiple rounds, where the former cannot be well upper-bounded via the latter. In Appendix <ref>, we provide a concrete example showing this issue.

Note that the ultimate goal in complementarity-based privacy estimation is not the estimation of phase-error rate but the phase-error cardinality. To solve the convexity issue, we develop a sample-entropy method inspired by classical information theory [Shannon, 1948] for the evaluation of the phase-error cardinality directly. The sample entropy is a random variable with respect to a phase-error pattern, the whose expected value is determined by the Shannon entropy. The direct use of the sample entropy of the phase error has a divergence problem. As a workaround, we apply a regularisation trick to the phase-error probability function.

With all the above ingredients, we arrive at the final security analysis result. We summarize it in the following informal theorem and leave the formal one and detailed derivation in Appendix <ref>.

After $n$ rounds of quantum measurements in DIQKD, let the observed average Bell value be $\bar{S}$ and the number of key generation rounds be $m$. Given fixed constants $\xi\in(0,\frac{1}{2}),\,\varepsilon_{S},\varepsilon_{pe},\varepsilon_{pc}\in(0,1)$, except for a failure probability no larger than $\varepsilon_f=\varepsilon_{S}+\varepsilon_{pe}+\varepsilon_{pc}$, the privacy amplification cost can be upper-bounded,

\begin{equation}\label{eq:priamp}
\begin{split}
I_{pa}&\leq \frac{1}{1+2\delta_{p}'}\left\{mh\left[e_{p}^{\xi} (S_{est})\right] + n\delta_{h}\right\}-\log\varepsilon_{pc}, \\
\end{split}
\end{equation}

where $h(x)=-x\log x-(1-x)\log(1-x)$ is the binary entropy function, $S_{est}$ is the estimation of the expected Bell value,

\begin{equation}\label{Eq:SimBellEst}
\begin{split}
S_{est}=(1+2\delta_{S}')\bar{S} - \delta_{S}, \\
\end{split}
\end{equation}

$\delta_{p}', \delta_{h}= O\left(\sqrt{\frac{-\log\varepsilon_{pe}}{n}}\right), \delta_{S}', \delta_{S}= O\left(\sqrt{\frac{-\log\varepsilon_{S}}{n}}\right)$, and $e_{p}^{\xi} \left(S\right)$ is the regularised phase-error function,

\begin{equation}\label{Eq:RelaxPhaseErrorProb}
e_{p}^{\xi}(S) = \dfrac{e_{p}(S) + \xi}{1+2\xi},
\end{equation}

with $e_p(S)$ given in Eq. (<ref>). Suppose the key length after information reconciliation is $I_{AB}$, the amount of generated key bits is given by $k=I_{AB}-I_{pa}$.

The estimation failure probabilities $\varepsilon_{S}$ and $\varepsilon_{pe}$ are introduced by Kato's concentration inequality, for the Bell test and phase errors, respectively. The terms $\delta_{h},\delta_{p}',\delta_{S}$ and $\delta_{S}'$ can be optimised. The realization of privacy amplification has a failure probability $\varepsilon_{pc}$. The parameter $\xi$ is introduced to avoid divergence of the sample-entropy function. Under fixed protocol parameters, the value of $\xi$ can be optimized and approaches zero when the data size is large.

Simulation. —We consider an experimental set-up designed according to the ideal setting while suffering from noise and loss. Ideally, the entanglement source prepares Bell state $\ket{\Phi^+}=(\ket{00}+\ket{11})/\sqrt{2}$, the key generation measurements are $\hat{A}_2=\hat{B}_0=\hat{\sigma}_z$, and the rest measurements are the ones giving the largest expected Bell value $S=2\sqrt{2}$. In entanglement distribution, the Bell state undergoes a depolarizing channel before measurement, characterised by $\hat{\mathcal{E}}_d[\rho] = (1-e_d)\rho + e_d \hat{I}/{4}$ with $e_d$ being the depolarising factor. The fidelity of the noisy state $\rho$ to the ideal state $\ket{\Phi^+}$ is calculated by $F(\rho,\Phi^+)=\bra{\Phi^+}\rho\ket{\Phi^+}=1-3e_d/4$. This model is close to the realistic case of entanglement distribution with a fiber link [Li et al., 2021].
Denote the total transmittance of the quantum signals on one side to be $\eta$. That is, with probability $(1-\eta)$, no detection is made. In a standard protocol, the users assign the undetected events a value of $1$. Alice and Bob randomly choose the measurement settings. We fix the total failure probability of the protocol to $\varepsilon_f=5\times10^{-11}$.

In the experiment, we need to determine the feasible regions of parameters $\eta$ and $e_d$ that render a positive key rate. The simulation result is shown in Fig. <ref>. In the attached tables, we list the tolerable channel-noise levels and the threshold transmittance for a positive key rate.
As shown by the feasible experimental regions in Fig. <ref>, the complementarity approach exhibits a fast convergence to the asymptotic limit of infinite data size. The asymptotic limit is consistent with the result assuming i.i.d. attacks [Pironio et al., 2009].

77Tolerable Noise
$n$     $\max{e_d}$

$10^6$     $0.102$

$10^7$     $0.129$

$10^8$     $0.138$

$\infty$     $0.143$

77Transmittance Threshold

$n$     $\min{\eta}$

$10^6$     $94.6\%$

$10^7$     $93.1\%$

$10^8$     $92.6\%$

$\infty$     $92.3\%$

Simulation results of key-generation performance with $\eta_A=\eta_B=\eta$.

The bottom right corner under each line represents the feasible region of experimental parameters $\eta,e_d$. For $n\rightarrow\infty$, we depict the feasible region in green.

To better examine the finite-size performance, we consider an experimental setting close to the cold-atom and nitrogen-vacancy-center platforms. For these platforms, the efficiency can be close to 1 with heralding. Meanwhile, the depolarizing factor can be controlled down to a reasonable level. The bottleneck lies in the data size required for the experiment, where the successful heralding rate of entangled pairs is normally very low, typically, on the order of tens of pairs per minute. For this purpose, we simulate the smallest data sizes that are required under different values of depolarizing factors, as shown in Fig. <ref>. In comparison, we simulate the data sizes required by the existing entropy-based analysis adopting the entropy accumulation theorem (EAT), including the original method [Arnon-Friedman et al., 2018] and a modified result [Murta et al., 2019]. The min-tradeoff function in the EAT analyses shares a similar position as the phase-error sample entropy in the complementarity-based analysis. The simulation results show that our method is more advantageous in saving experimental time. For instance, at $e_d=10\%$, which corresponds to a state preparation fidelity of $92.5\%$, a reasonable experimental parameter achievable by state-of-the-art cold-atom [Rosenfeld et al., 2017, Zhang et al., 2022] and nitrogen-vacancy-centre [Hensen et al., 2015] platforms, the original EAT method $6.16\times10^8$ rounds and the modified EAT method requires $2.75\times10^7$ rounds for positive key generation. In comparison, our security analysis cuts down the experimental time by two orders, requiring $9.12\times10^5$ rounds, making a DIQKD realization on these experimental platforms plausible within a reasonable time under decent security parameters. With a larger depolarizing factor, the advantage of our result becomes more significant. We find a similar behavior for the relation between the least required data sizes and transmittance.

We also compare our method with the state-of-the-art EAT analysis, which utilizes second-order statistics to improve the finite-size performance [Liu et al., 2021]. Using the variance information of the distributions, the advanced EAT method drastically reduces the data size. With this advanced method, recently, a full DIQKD experiment was achieved on an ion-trap platform [Nadlinger et al., 2022]. Under an average Bell value of $\bar{S}=2.64$ and a quantum bit error rate of $e_b=1.8\%$, the experiment produces the first secure key bit after approximately $10^6$ rounds of measurements (see Fig. 4 in the cited reference). The correspondence between this method and the current complementarity-based method is less clear, as we have not utilized the variance information. Even without this technique, the complementarity-based method still exhibits better finite-size performance. The least data required for key generation could be shortened to approximately $3.16\times10^5$ rounds, less than one-third of that required by the EAT method.

The smallest data sizes required for successful key generation with respect to different depolarising factors at $\eta=1$.

One main reason for the advantage in the finite-size regime is that our approach has a tighter bound on the information leakage of classical postprocessing. In the EAT-type analyses, the entropy that reflects the key secrecy is accumulated round by round in the experiment via a Markov chain [Arnon-Friedman et al., 2018, Liu et al., 2021]. The classical communication for Bell-value evaluation also contributes to the entropy accumulation. Consequently, the users need to cost extra secret keys to compensate for the information leakage. On the contrary, our method bypasses the above issue. Along the complementarity approach, the users can freely transmit classical information for parameter estimation as long as it does not affect the phase-error cardinality in key generation rounds. In fact, the information leakage in test rounds is not so pessimistic as in the EAT analysis. Without the additional consumption of private keys, the users can expect positive key generation in a shorter time. In Appendix <ref>, we provide the simulation model, more numerical results, and more discussions comparing the two approaches.

Advantage Key Distillation. —Due to the operational meaning of measurement complementarity, we can employ three advantage key distillation methods, namely, noisy pre-processing (N) [Kraus et al., 2005], usage of loss information (L) [Ma and Lütkenhaus, 2012], and B-step via two-way classical communication (B) [Gottesman and Lo, 2003, Chau, 2002], to DIQKD without the i.i.d. assumption. We also consider the protocol using both noise pre-processing and loss information (C). Their improvement over the standard protocol (S) can be explicitly traced by the change in phase-error cardinality. These advantage methods can effectively increase the tolerable noise, reduce the minimum requirement on state fidelity, and lower the threshold of total transmittance, as shown in Table <ref>. Under the assumption of i.i.d. attacks, the methods have been considered in the literature. We obtain the same threshold values for the methods of (L) [Ma and Lütkenhaus, 2012] and (N) [Ho et al., 2020], and a similar result for (B) to the usage of repetition code [Tan et al., 2020], where the reported threshold transmittance is $89.1\%$. We now strengthen the results as they become applicable to the most general attacks. We present the details for the advantage key distillation methods in Appendix <ref> and simulation results in Appendix <ref>.

Thresholds of transmittance and fidelity for different postprocessing. We calculate the threshold transmittance with the fidelity set to unity and vice versa.

Protocol     Threshold Transmittance     Threshold Fidelity

(S)     $92.36\%$     $89.28\%$

(N)     $91.27\%$     $87.88\%$

(L)     $90.87\%$     $89.28\%$

(C)     $90.47\%$     $87.88\%$

(B)     $88.30\%$     $88.28\%$

Outlook. —Based on the complementarity approach, our security analysis explicitly shows the role of measurement complementarity in device-independent quantum cryptography. We focus on the sequential DIQKD protocol using the CHSH test. A natural extension is the parallel setting, where the legitimate users input all the measurement settings at once and then obtain all measurement results [Jain et al., 2020]. In practice, it would also be meaningful to explore whether Bell tests other than the CHSH test are more advantageous under certain realistic conditions [Eberhard, 1993]. In addition to the cryptography tasks, complementarity analysis could be immediately used for device-independent distillable entanglement quantification. In privacy estimation, we generalize the concept of sample entropy from classical Shannon theory. To the best of our knowledge, this is the first time that sample entropy has been used for QKD parameter estimation. We believe that the sample entropy will find more use in other areas of quantum science.

Acknowledgments. —We acknowledge Hongyi Zhou, Go Kato, Rong Wang, and Chenyang Li for the insightful discussions on concentration inequalities, Toyoshiro Tsurumaru and Charles L.-C. Wen for discussions on related works, Ernest Tan for discussions on the memory effect, Yizhi Huang for independently checking the numerical results, Zhiqiang Liu and Zhenhuan Liu for contributions during early stages of this project, and Guoding Liu and Junjie Chen for the careful proofread. This work is supported by the National Natural Science Foundation of China Grant No. 11875173, the National Key Research and Development Program of China Grant No. 2019QY0702 and No. 2017YFA0303903, NSERC, CFI, ORF, Connaught Innovation Award, MITACS, the Royal Bank of Canada, Huawei Technologies Canada, Inc. and the University of Hong Kong start-up funding.

§ NOTATIONS

Frequently used parameters, random variables, and quantum operators in this work.

Notation     Meaning     Relation to Other Quantities

$n$     number of rounds of quantum measurements

$[n]$     $\{1,\cdots,n\}$

$\mathbb{N}$     set of natural numbers (including $0$)

$\mathbb{C}$     set of complex numbers

$\mathcal{L}(\mathcal{H})$     set of linear operators defined on the Hilbert space $\mathcal{H}$

$\mathcal{D}(\mathcal{H})$     set of density operators defined on the Hilbert space $\mathcal{H}$

$f_{ec}$     efficiency in information reconciliation

$x_i\in\{0,1,2\}$     Alice's input random variable in the $i$th round

$y_i\in\{0,1\}$     Bob's input random variable in the $i$th round

$a_i\in\{1,-1\}$     Alice's output random variable in the $i$th round

$b_i\in\{1,-1\}$     Bob's output random variable in the $i$th round

$p_X$     Alice's input probability distribution

$p_Y$     Bob's input probability distribution

$\lambda_i$     system random variable (value) of the $i$th round

$\kappa^A$     Alice's raw key bit string

$\kappa^B$     Bob's raw key bit string

$\hat{\Pi}_{\lambda_i}^A$     projector onto the subspace $\mathcal{H}_A^{\lambda_i}$

$\hat{\Pi}_{\lambda_i}^B$     projector onto the subspace $\mathcal{H}_B^{\lambda_i}$

$\rho_{\lambda_i}^{AB}\in\mathcal{D}(\mathcal{H}_A^{\lambda_i}\otimes\mathcal{H}_B^{\lambda_i})$     underlying subsystem in the $i$th round corresponding to the system random variable value $\lambda_i$

$\hat{A}_x^{\lambda_i}\in\mathcal{L}(\mathcal{H}_A^{\lambda_i}),x\in\{0,1\}$     observable in the $i$th round corresponding to Alice's input $x$ and system random variable value $\lambda_i$

$\hat{A}_2^{\lambda_i}\in\mathcal{L}(\mathcal{H}_{A(i)})$     observable in the $i$th round corresponding to Alice's input $x=2$

$\hat{B}_y^{\lambda_i}\in\mathcal{L}(\mathcal{H}_B^{\lambda_i}),y\in\{0,1\}$     observable in the $i$th round corresponding to Bob's input $y$ and system random variable value $\lambda_i$

$\hat{A}_{\theta_i}^{\lambda_i}\in\mathcal{L}(\mathcal{H}_A^{\lambda_i})$     auxiliary observable on Alice's side in the $i$th round corresponding to the system random variable value $\lambda_i$

$\hat{B}_{\bot}^{\lambda_i}$     complementary observable of $\hat{B}_0^{\lambda_i}\in\mathcal{L}(\mathcal{H}_B^{\lambda_i})$     $\{\hat{B}_{\bot}^{\lambda_i},\hat{B}_0^{\lambda_i}\}=0$

$\hat{S}^{\lambda_i}$     Bell observable in the $i$th round corresponding to the system random variable value $\lambda_i$     $\hat{S}^{\lambda_i} = \sum_{x,y\in\{0,1\}}(-1)^{xy}\hat{A}_{x}^{\lambda_i}\otimes \hat{B}_{y}^{\lambda_i}$

$S^{\lambda_i}$     expected Bell value in the $i$th round corresponding to the system random variable value $\lambda_i$     $S^{\lambda_i}=\Tr(\rho_{\lambda_i}^{AB}\hat{S}^{\lambda_i})$

$E_{p}^{\lambda_i}\in\{0,1\}$     phase-error random variable in the $i$th round corresponding to the system random variable value $\lambda_i$

$e_{p}^{\lambda_i}\in[0,\frac{1}{2}]$     phase-error probability in the $i$th round corresponding to the system random variable value $\lambda_i$

$\Delta_{p}^{(i)}$     martingale random variable constructed from phase-error random variables in the $i$th round     Eq. (<ref>), see also the definition of $\zeta_{p}^{(i)}$ in Eq. (<ref>)

$\Delta_{xy}^{(i)},x,y\in\{0,1\}$     martingale random variable with respect to the measurement setting $(x,y)$ constructed from Bell test random variables in the $i$th round     Eq. (<ref>), see also the definition of $\zeta_{xy}^{(i)}$ in Eq. (<ref>)

$\xi\in(0,\frac{1}{2})$     regularisation parameter in the regularised sample entropy

$\varepsilon_{pe}\in(0,1)$      failure probability in the phase-error sample entropy estimation

$\varepsilon_{xy}\in(0,1)$     failure probability in the parameter estimation of the Bell test setting $(x,y)$

$\varepsilon_{S}\in(0,1)$     failure probability in the parameter estimation of the Bell value     $\varepsilon_{S}=\sum_{x,y=0,1}\varepsilon_{xy}$

$\varepsilon_{pc}\in(0,1)$     failure probability in privacy amplification

Before we commence, we explain the notations in this work. Some frequently used notations are listed in Table <ref>.

* The letters $A,B,E$ are used to specify the quantum systems of Alice, Bob (legitimate users), and Eve (adversarial party). We denote the Hilbert spaces that the quantum operators act on as $\mathcal{H}$ and use subscripts and superscripts to specify subsystems.

* Except in Sec. <ref>, for simplicity, we usually express random variables by lowercase English or Greek letters. In most cases, we do not express the underlying probabilistic spaces explicitly. We shall make it clear if lowercase letters represent abstract but specific values or realisations of random variables. Nevertheless, to keep in accordance with convention, we shall always use $E_p\in\{0,1\}$ to represent the phase-error random variable, $e_p$ to represent the phase-error probability and $S$ to represent the Bell value. In cases where the realisation of $E_p$ matters, we shall explicitly express it. For instance, we denote $E_p=1$ as the occurrence of a phase error.

In Sec. <ref>, we develop a martingale-based finite-size analysis. For this part, we shall rigorously distinguish the concepts of random variables, the sample space of a random variable, and realisations of a random variable. For English letters (except $E_p$ and $S$), we use the expression in the form $X=x\in\mathcal{X}$ to represent the following meaning: a random variable, of which the sample space is $\mathcal{X}$, takes the realisation $x$ in an experiment. Whether the letters $A,B,E$ represent random variables or systems should be clear from the context. We use a similar expression for $\Lambda=\lambda$, where the random variable $\Lambda$ represents the system variable in this paper. For other Greek letters that are related to the martingale analysis, we shall explicitly explain whether they shall represent a random variable or a specific realisation of it.

* For quantum operators, $\rho$ is kept for the density matrix of the state of a quantum system. Quantum channels or measurements letters acting on a quantum system are represented with capital letters with a hat notation.

* If there is a group of quantum operators or random variables of similar meaning, we shall use their subscripts and (or) superscripts to specify them. A common case is to specify the round number. For example, $\rho_i$ represents the quantum state in the $i$th round. If the round number needs to be displayed together with other notations, we shall denote the round number by the subscript with a bracket, $(i)$, in case of ambiguity. If the round number value can be embedded in another random variable's value without confusion, we shall omit the subscript $(i)$. For example, in the notation $\rho_{\lambda_i}$, the round number is incorporated into the notation $\lambda$. In this case, $\rho$ needs to be specified by both $\lambda$ and $i$, and $i$ is also used for the specification of $\lambda$.

* There are notations that do not follow the above explanation. They will be explicitly explained when they appear for the first time.

In addition, we list the representations of the Pauli operators used in this work,

\begin{equation}
\hat{\sigma}_x = \left(\begin{matrix}
0 & 1 \\
1 & 0
\end{matrix}\right),
\hat{\sigma}_y = \left(\begin{matrix}
0 & -i \\
i & 0
\end{matrix}\right),
\hat{\sigma}_z = \left(\begin{matrix}
1 & 0 \\
0 & -1
\end{matrix}\right),
\end{equation}

where we represent them on the computational basis determined by the eigenvectors of $\hat{\sigma}_z$, and $i^2=-1$. We use $H(\cdot)$ to represent the Shannon entropy function or the von Neumann entropy function. If the argument is a random variable, the Shannon entropy is given by

\begin{equation}
\end{equation}

where $X\in\mathcal{X}$ denotes the random variable, and $p_X$ denotes its probability mass function. For $p_X(x)=0$, we take the convention of $0\log 0\equiv0$. If the argument is a density operator, i.e., a positive semi-definite operator with a unit trace, the von Neumann entropy is given by

\begin{equation}
\end{equation}

where $\{\lambda_i\}_{i\in\mathcal{I}}$ are the eigenvalues of $\rho$. Throughout this work, the logarithm function $\log$ is assumed to be base 2 and $\ln$ is the logarithm function with base $e$. For a binary random variable, the Shannon entropy becomes the binary entropy, which is defined as

\begin{equation}
h(x)=-x\log x-(1-x)\log(1-x),
\end{equation}

with $x\in[0,1]$.

§ PROTOCOL AND SECURITY STATEMENTS

In establishing the security analysis, we consider the device-independent quantum key distribution (DIQKD) protocol given in Box <ref>. The protocol was originally proposed in Ref. [Acín et al., 2006]. For simplicity, we denote this protocol as the `standard protocol'. Later in Sec. <ref>, we shall consider several modified protocols with advantage key distillation based on the standard protocol.

[label=box:ProtocolDetail]DIQKD Protocol (Standard Protocol)

$n$: the number of rounds of quantum measurements

$\{p_X(x)\}_x,\,\{p_Y(y)\}_y$: probability distributions for the basis choices

* Measurement: For every round $i\in[n]$, Alice and Bob

* randomly set measurement bases $x_i\in \{0,1,2\},y_i\in \{0,1\}$ with probability distributions $p_X,p_Y$;

* record the outputs of the devices $a_i \in \{\pm1\},b_i \in \{\pm1\}$.

* Parameter Acquisition: Alice and Bob obtain the following parameters in the experiment

* the number of rounds $m_{xy}$ with inputs $(x_i,y_i) = (x,y)\in\{0,1\}\times\{0,1\}$ and $m$ with $(x_i,y_i) = (2,0)$;

* for $(x_i,y_i)=(2,0)$, the number of positions $q$ where $a_i\neq b_i$;

* for $(x_i,y_i) = (x,y)\in\{0,1\}\times\{0,1\}$, the number of positions $q_{xy}$ where $(-1)^{x\cdot y}a_i\cdot b_i=-1$.

* Raw Key Acquisition: Alice and Bob obtain the bit strings $\kappa^A,\kappa^B$ from $a_i,b_i$ with $(x_i,y_i)=(2,0)$.

* Privacy Estimation: Alice and Bob estimate the key privacy with statistics acquired in Step 2, (c).

* Key Distillation: Alice and Bob

* reconcile the bit strings to $\kappa^B$ through an encrypted classical channel except for failure probability $\varepsilon_{ec}$;

* apply a privacy amplification to $\kappa^B$ and derive the final key except for failure probability $\varepsilon_{pc}$.

Referring to the notations in Theorem <ref> of the main text, the bit error rate and the observed average Bell value are given as

\begin{equation}\label{Eq:biterrorrate}
\begin{aligned}
e_b&=\frac{f(a\neq b,x=2,y=0)}{p_{X}(2)p_{Y}(0)},
\end{aligned}
\end{equation}

\begin{equation}\label{eq:Sexpobs}
\bar{S} = \sum_{x,y\in\{0,1\}}\frac{m_{xy}-2q_{xy}}{np_X(x)p_Y(y)}.
\end{equation}

where $f(\cdot)$ is the frequency of the realisation.

We clarify the notions round and session in this work. When referring to a round, we mean one complete quantum measurement in Step 1. A round starts when Alice and Bob set the measurement bases and ends when their devices generate outputs. A complete run of the protocol is referred to as a session. A session ends either Alice and Bob abort in advance, or they obtain a final key.

In the security analysis, we consider the most general sequential condition. That is, in Step 1 of the protocol, Alice and Bob shall not start the $(i+1)$th round until they have finished the $i$th round. The measurement results might be dependent on the previous events. In particular, the probabilities of the outputs might not be independent and identically distributed (i.i.d.). The inner working of the quantum devices is not characterised in prior, except for the following assumptions/requirements:

* Quantumness: Quantum mechanics is correct.

* Non-Signalling: No information is communicated between Alice and Bob's devices in a round.

* Trusted Inputs: The users have trusted local private randomness for the bases choices.

* Reliable Classical Module: The users have reliable key management and authenticated channels for classical communication.

We impose the assumption of reliable key management to prevent the devices from leaking the key information to an adversary. To ensure this, we assume that except for the public classical information exchange necessary for the classical phase, the devices of Alice and Bob signal no other information to the outside. In practice, though, this assumption would technically guarantee the second assumption, as the inputs and outputs on the one side can be kept away from the other side in the same way they are kept secret from the outside. Still, we can relax the constraint on the communication between Alice and Bob's devices in the security analysis, where the devices are allowed to communicate with each other between two adjacent rounds.

In this work, we consider that the devices are only used for one complete session. If the devices are reused for multiple sessions of DIQKD, the memory loophole might exist. That is, the untrusted devices may store the key information in one DIQKD session and leak it via the necessary public communication required by the protocol when they are reused in new sessions [Barrett et al., 2013]. There exist practical defences against the memory attacks [Barrett et al., 2013, Curty and Lo, 2019]. In this work, we do not discuss this point. It should be noted that in a single session, the memory attack does not take place. In particular, the quantum measurements can be dependent on all possible information generated in the previous rounds on both sides. Our security analysis applies to this general condition.

Suppose after running the protocol, Alice and Bob obtain their $k$-bit key strings, $\tilde{\kappa}^A$ and $\kappa^B$, respectively. We use $\tilde{\kappa}^A$ to distinguish Alice's final key from her raw key $\kappa^A$. The final key state is described by a classical-classical-quantum state,

\begin{equation}
\rho_{ABE}=\sum_{\tilde{\kappa}^A,\kappa^B}\Pr(\tilde{\kappa}^A,\kappa^B)\ketbra{\tilde{\kappa}^A}\otimes\ketbra{\kappa^B}\otimes\rho_E(\tilde{\kappa}^A,\kappa^B),
\end{equation}

where system $E$ represents the quantum side information. From an adversarial perspective, the key bits of the legitimate users are characterised by random variables of the systems $A,B$. Ideally, the final key state should be

\begin{equation}
\rho_{ABE}^{ideal}=2^{-k}\sum_{\kappa}\ketbra{\kappa}_A\otimes\ketbra{\kappa}_B\otimes\rho_E,
\end{equation}

where Alice and Bob's keys are perfectly identical and appear fully random to the outside. The protocol security is defined as the difference between the actual key state and the ideal key state.

A QKD protocol is called $\varepsilon_{QKD}^s$-secret, if for a successful implementation of the protocol,

\begin{equation}
\frac{1}{2}(1-p_{abort})\|\rho_{ABE}-\rho_{ABE}^{ideal}\|_1\leq\varepsilon_{QKD}^s,
\end{equation}

where $p_{abort}$ is the probability that the protocol aborts, and $\|A\|_1=\Tr(\sqrt{A^\dag A})$ is the trace norm.

Here, the parameter $\varepsilon_{QKD}^s$ is also called the soundness error. The parameter $p_{abort}$ is linked with another security parameter, namely, the completeness error. We remark that soundness and completeness are different notions. Roughly speaking, it is the soundness error that corresponds to the privacy of generated keys. On the other hand, completeness guarantees that the legitimate users can obtain keys (possibly not private) with a high probability. In the context of QKD, the completeness issue can often be neglected. We shall come to this point later in Sec. <ref>.

Generally, after a complete session, the net increase of secure key bits shall be given by

\begin{equation}
k = m - I_{ir} - I_{pa},
\end{equation}

where $I_{ir}$ and $I_{pa}$ are the costs of pre-shared private randomness, or secret keys, for information reconciliation and privacy amplification, respectively. Security analysis aims at the determination of their values. The two terms can be correlated with each other. We analyse the DIQKD security under the framework of complementarity-based quantum error correction protocol [Koashi, 2009]. Under this framework, we aim at establishing a virtual protocol as follows:

[label=box:KoashiVirtual]Virtual Protocol in Complementarity Approach [Koashi, 2009]
Alice and Bob run the following procedures to achieve a final secure key.

* Initialise the system in joint state $\rho^{AB}$;

* Apply operation $\hat{\Pi}$ on $\rho^{AB}$ such that $\hat{\Pi}(\rho^{AB})\in\mathcal{D}(\mathcal{K}^{\otimes m}\otimes\mathcal{H}_R)$, where $\dim{\mathcal{K}}=2$;

* Measure system $\mathcal{K}^{\otimes m}$ on the computational basis, denoted as $Z$-basis, and obtain $\kappa_{rec}$;

* Measure system $\mathcal{H}_R$ with $\hat{M}_R$ and obtain result $\gamma$, which determines $I_{pa}$;

* Apply hashing on $\kappa_{rec}$ and obtain the final key $\kappa_{fin}$ with length of $(m-I_{pa})$ bits.

If we can establish such a virtual protocol that meets certain security requirements, then there exists a data post-processing procedure for the raw data in the real experiment that produces a secret key with a negligible failure probability. This result is given in Ref. [Koashi, 2009], which we summarise as follows [There is an error in the security parameter in the original work of Ref. [Koashi, 2009] due to the definition of fidelity measures. This is later corrected in Ref. [Fung et al., 2010]].

With respect to the actual QKD protocol in Box <ref>, if one can set up a corresponding virtual protocol in Box <ref>, where the chosen operation $\hat{\Pi}$ and measurement $\hat{M}_R$ in the virtual protocol meet the following requirements:

* the $Z$-basis measurement statistics $\kappa_{rec}$ in the virtual protocol is the same as reconciled key $\kappa^B$ in the actual protocol;

* given each outcome $\gamma$ of measurement $\hat{M}_R$, had a measurement on the complementary basis of the $Z$ basis been taken on $\mathcal{K}^{\otimes m}$, the number of measurement outcomes can be upper bounded by $2^{T}$ except for failure probability $\varepsilon_{pe}$,

then the actual protocol is $\sqrt{\varepsilon(2-\varepsilon)}$-secret and $\varepsilon_{ec}$-correct, where $\varepsilon=\varepsilon_{pe}+\varepsilon_{pc}$ and $I_{pa}=T-\log\varepsilon_{pc}$.

In this security statement, the failure probability has the operational meaning of state fidelity. In Step 3 of the virtual protocol, suppose before the $Z$-basis measurement, the joint state becomes $\ket{0}_X^{\otimes m}$, an eigenstate of an observable complementary to the $Z$-basis measurement. Then, the $Z$-basis measurement result shall be intrinsically random and hence private from the outside. In establishing the security statement [Koashi, 2009] for a general case, the privacy amplification is recast into a quantum error correction protocol that distills such a state with local operations and classical communication (LOCC). Conditioned on $\gamma$, the complementary measurement gives one of the eigenstates on $X$-basis. If the number of possible outcome patterns can be upper-bounded as stated by the second requirement in Lemma <ref>, then there exists an error correction protocol for Alice and Bob to correct the state to $\ket{0}_X^{\otimes m}$. For the purpose of error correction, a general linear error correction code suffices [Lo, 2003, Huang et al., 2021]. In practice, privacy amplification can be efficiently carried out by using the family of two-universal hashing functions [Fung et al., 2010]. Suppose in the virtual quantum error correction protocol, the output state is $\rho_{\mathcal{K}}$. It is proved that the state fidelity of $\rho_{\mathcal{K}}$ to $\ket{0}_X^{\otimes m}$ is linked to the failure probability of the post-processing procedures,

\begin{equation}\label{Eq:FidelitySec}
\Tr(\rho_{\mathcal{K}}\ketbra{0}_X^{\otimes m})\geq 1-\varepsilon.
\end{equation}

In Ref. [Fung et al., 2010], it is proved that the security parameter given by the fidelity measure can be linked to the trace-distance-based security definition. Measuring the state $\rho_{\mathcal{K}}$ with key generation measurement, the key is $\sqrt{\varepsilon(2-\varepsilon)}$-sound by Definition <ref>. In the virtual quantum error correction protocol, the users need to communicate with each other the information of quantum error syndromes. They consume private randomness for this step, and the amount of private randomness corresponds to the privacy amplification cost, $I_{pa}$.

To simplify the statements in the complementarity-based security analysis, we introduce the notion of phase errors. We describe the measurement of complementary observable given $\gamma$ as the phase-error measurement and denote a specific outcome as a phase-error pattern. With respect to the ideal case $\ket{0}_X^{\otimes m}$, if the phase-error measurement result on the $i$th bit differs from $0$, then we say that a phase error occurs on this bit. Given an underlying system, there exists a smallest set of phase-error patterns that will occur except for a negligible failure probability. Denote the number of these patterns as the phase-error cardinality under the given failure probability. The second requirement in Lemma <ref> represents an upper bound on the phase-error cardinality.

Another issue in this security statement is that information reconciliation and privacy amplification can be decoupled. This can be done by encrypting the error syndromes in classical communication of information reconciliation [Lo, 2003]. Information reconciliation, essentially the problem of key agreement, can be well solved efficiently via classical means [Brassard and Salvail, 1994]. At the moment, we assume that Alice and Bob apply one-way information reconciliation, and the outputs of $a_i,b_i$ in the key generation rounds are taken as the raw key bit strings $\kappa^A,\kappa^B$. Bob hashes his bit string and sends the hashing results to Alice through an encrypted classical channel. In this step, $I_{ir}$ bits of pre-shared keys are consumed for encryption. Based on the received message, Alice can reconcile her bit string $\kappa^A$ to $\kappa^B$. We denote the reconciled key length as

\begin{equation}
I_{AB} = m - I_{ir},
\end{equation}

which is the net increase of identical bits after the information reconciliation. In the Shannon limit, the cost of private randomness is

\begin{equation}
\lim_{n\rightarrow\infty} I_{ir} = H(\kappa^B|\kappa^A).
\end{equation}

In principle, the Shannon limit can be reached in the asymptotic limit of infinite data size with proper design of encoding and decoding schemes. In practice, the cost becomes

\begin{equation}\label{Supp:InfoRec}
I_{ir} = f_{ec}H(\kappa^B|\kappa^A),
\end{equation}

where $f_{ec}\geq1$ is an efficiency factor depending on the specific encryption code that is used. Much effort has been made in designing practical error-correcting codes and schemes for encoding and decoding. Except for the discussion in Section <ref>, in the numerical simulations in this work, for simplicity, we take the Shannon limit where $f_{ec}\rightarrow1$. For a more practical discussion, we would like to refer the readers to the recent state-of-the-art results [Tang et al., 2021]. If an error occurs with same probability for the two bit values, we have $H(\kappa^B|\kappa^A) = mh(e_b)$, where $e_b\equiv q/m$ is the bit error rate, which is the average difference between Alice and Bob's raw key bits. We note that this symmetric case can always be met, as Alice and Bob can have a public discussion and flip some of their raw bits. Nevertheless, this would result in the loss of the amount of reconciled key bits.

§ OUTLINE OF SECURITY ANALYSIS

The evaluation of the privacy amplification cost, $I_{pa}$, is the essence of security analysis. To apply the complementarity framework to DIQKD, we shall

* define phase-error measurement in the device-independent scenario;

* estimate the phase-error cardinality via the observed statistics.

The solutions to the two problems provide the ingredients for the virtual protocol in Box <ref>. The solution to the first problem gives the construction of $\hat{\Pi}$ and $\hat{M}_R$. To tackle the problem, we take advantage of Jordan's lemma and effectively reduce the quantum systems in each round to qubits [Pironio et al., 2009]. Then, we can apply the mature techniques in regular QKD to define phase-error measurement.

To solve the second problem, we adopt the idea of breaking the general non-i.i.d. correlation into the analysis of single rounds. We divide the task into the following steps,

* relating the phase-error probability with the expected Bell value in each round;

* finding a measure of the phase-error cardinality that relates to the phase-error probability;

* extending the single-round result to multiple rounds and deriving the estimation of the phase-error cardinality.

For the first step, we derive an analytical relation between the expected values. For the second step, one might naively use the phase-error rate, a well-studied and commonly-used privacy measure in regular QKD. Unfortunately, as we shall explain later, this is not a good measure in DIQKD. Instead, we generalise the concept of sample entropy from classical Shannon theory: we prove that this provides a good measure of the phase-error cardinality. For the third step, we show that the sequential setting allows for a martingale-based analysis. In this step, the random basis setting in DIQKD plays a vital role. By combining the results, we obtain an analytical upper bound on the cost of privacy amplification in terms of the observed average Bell value.

In Figure <ref> we demonstrate the key technical steps towards the key privacy estimation.

The flowchart of the security analysis steps in privacy estimation.
(1) System characterisation: In the first step, the quantum system needs to be defined. Due to the simplicity of our protocol, we can analyse the problem with an effective qubit system for each single round. We shall also model the possible correlations over rounds and define the underlying physical quantities, especially the expected Bell value.
(2) Phase error definition: Based on the system characterisation results, the measurement complementary to the key generation measurement is defined. This allows us to introduce a virtual protocol to estimate the key privacy. In the virtual protocol, the phase-error operation is defined, and the probability a phase error occurs is linked with the expected Bell value.
(3) Privacy estimation: We estimate the key privacy by upper bounding the number of possible phase-error patterns over multiple rounds, or, the cardinality of the phase error set. We construct the statistics of phase-error sample entropy for this task. As the random variables might not be independent and identically distributed, Azuma's inequality is used to link the expected values and probabilities with frequencies.

§ SYSTEM MODELLING

In this section, we model the quantum system and measurement in the sequential DIQKD protocol. Also, we briefly review a few standard techniques developed in the field of quantum self-testing that are used in our security analysis.

§.§ General sequential setting

In DIQKD, the legitimate users do not have access to the internal working of the uncharacterised devices but only the input-output statistics accumulated from the outside. Under the framework of quantum mechanics, the underlying physical processes can be described by quantum measurements. We analyse the security under the most general sequential measurement setting. Without loss of generality, DIQKD can be described by a sequential quantum process in Figure <ref>. In an adversarial picture, the quantum systems and measurement devices are provided by a potentially malicious party, Eve. After the protocol begins, Eve no longer has access to Alice's or Bob's devices. Nevertheless, she could prepare her quantum system correlated with Alice and Bob's joint system in prior. In the worst-case scenario, Eve could hold the purification of the initial state of Alice and Bob's joint system before measurement.

In sequential DIQKD, the measurement process is restricted to a specific time order noted by rounds. The state and measurement of a round cannot depend on the inputs and outputs of future rounds. From the $i$th round to the $(i+1)$th round of DIQKD, Alice and Bob's system evolves as follows.

* At the beginning of the $i$th round, Alice and Bob's joint system is in a bipartite state, $\rho_{i}^{AB}\in\mathcal{D}(\mathcal{H}_{A_i}\otimes\mathcal{H}_{B_i})$. In general, state $\rho_{i}^{AB}$ depends on all information generated in the previous rounds, including both the data accessible to Alice and Bob, $\{x_{j},y_{j},a_{j},b_{j}\}_{j=1}^{i-1}$, and any other possible hidden information of the untrusted devices inaccessible to the users, together denoted by $\lambda_{i}$ with $\lambda_{1}$ denoting the initial hidden variable of the system.

* Depending on the basis choices, $x_i,y_i\in\{0,1\}$, Alice and Bob perform general measurements on systems $\mathcal{H}_{A_i}$ and $\mathcal{H}_{B_i}$, independently, and then obtain classical outputs $a_i,b_i\in\{-1,1\}$. Alice and Bob's quantum operators could also depend on $\lambda_{i}$. Since there is no restriction on the system dimensions, the measurement operators can be projections due to the Neumark extension [Neumark, 1940], denoted by two observables, $\hat{A}_{x_i}$ and $\hat{B}_{y_i}$. Due to the non-signalling condition, they take a tensor-product form, $\hat{A}_{x_i}\otimes\hat{B}_{y_i}$. This is the main assumption in the Bell test, often guaranteed by space-like separation.

* A general channel $\hat{T}_i$ is applied to the post-measurement state. The state of the system becomes $\rho_{i+1}^{AB}\in\mathcal{D}(\mathcal{H}_{A_{i+1}}\otimes\mathcal{H}_{B_{i+1}})$ and is passed on to the $(i+1)$th round. Between two adjacent rounds, we do not restrict Alice's and Bob's devices from communicating with each other and sharing past events, but not with Eve. As a result, measurement $\hat{A}_{x_i}\otimes\hat{B}_{y_i}$ and operation $\hat{T}_i$ together transform $\rho_i^{AB}$ to $\rho_{i+1}^{AB}$.

[circle,fill,gray,inner sep=1pt,label=left:$\rho^{ABE}$] (orig) at (0,0) ;

[-] (orig) – (.5,1) node[right=.3,above]$\rho^E$ – ++(10.6,0);
[-] (orig) – (.5,-1) node[right=.3,above]$\rho^{AB}_1$ – ++(1.5,0);

[rectangle,draw=black,fill=green!10!white,minimum size=20pt] (op1) at (2,-1)

[->] ($ (op1) + (.3,.6) $) – ++(0,0.3) node[above]$a_1$;
[<-] ($ (op1) + (-.3,.6) $) – ++(0,0.3) node[above]$x_1$;
[->] ($ (op1) + (.3,-.6) $) – ++(0,-0.3) node[below]$b_1$;
[<-] ($ (op1) + (-.3,-.6) $) – ++(0,-0.3) node[below]$y_1$;
[rectangle,draw=black,fill=blue!10!white,minimum size=20pt,rounded corners] (T1) at (3.5,-1) $\hat{T}_1$;
[-] (op1.east) – (T1.west) node[midway,above] ;

[rectangle,draw=black,fill=green!10!white,minimum size=20pt] (op2) at (5.5,-1)

[->] ($ (op2) + (.3,.6) $) – ++(0,0.3) node[above]$a_2$;
[<-] ($ (op2) + (-.3,.6) $) – ++(0,0.3) node[above]$x_2$;
[->] ($ (op2) + (.3,-.6) $) – ++(0,-0.3) node[below]$b_2$;
[<-] ($ (op2) + (-.3,-.6) $) – ++(0,-0.3) node[below]$y_2$;
[rectangle,draw=black,fill=blue!10!white,minimum size=20pt,rounded corners] (T2) at (7,-1) $\hat{T}_2$;
[-] (T1.east) – (op2.west) node[midway,above] $\rho_{2}^{AB}$;
[-] (op2.east) – (T2.west) node[midway,above] ;

[] (dots) at (8.5,-1) $\cdots$;
[-] (T2.east) – (dots.west) node[midway,above] $\rho_{3}^{AB}$;

[rectangle,draw=black,fill=green!10!white,minimum size=20pt] (opn) at (10.2,-1)

[->] ($ (opn) + (.3,.6) $) – ++(0,0.3) node[above]$a_n$;
[<-] ($ (opn) + (-.3,.6) $) – ++(0,0.3) node[above]$x_n$;
[->] ($ (opn) + (.3,-.6) $) – ++(0,-0.3) node[below]$b_n$;
[<-] ($ (opn) + (-.3,-.6) $) – ++(0,-0.3) node[below]$y_n$;
[-] (dots.east) – (opn.west) node[midway,above] $\rho_{n}^{AB}$;
[-] (opn.east) – ++(.3,0);

System description of the sequential setting. Initially, the system of Alice and Bob is prepared in $\rho_1^{AB}\in\mathcal{D}(\mathcal{H}_A\otimes\mathcal{H}_B)$, which may be correlated or entangled with Eve's system, $\rho^E$. That is, $\rho_1^{AB}=\Tr_E(\rho^{ABE})$. In the $i$th round, the system of Alice and Bob to be measured is in the state of $\rho_i^{AB}$. Given the bases choices $x_i,y_i$ on each side, the measurement process is described by observables, $\hat{A}_{x_i}$ and $\hat{B}_{y_i}$, which yield the measurement results $a_i,b_i$. During the measurement process, no information can be communicated between Alice and Bob, as represented by the double lines. Between two adjacent rounds, communication is allowed between the measurement devices of Alice and Bob, characterised by a general quantum channel $\hat{T}_i$. Afterwards, the resulted state $\rho_{i+1}^{AB}$ becomes the input of the $(i+1)$th round.

Now, we can make the criteria raised by the sequential setting mathematically rigorous. First, define the conditional probability,

\begin{equation}
\begin{split}
\Pr(a_i,b_i|x_i,y_i,\lambda_{i}) &\equiv \Tr[\left(\hat{M}_{x_i}^{a_i}\otimes\hat{M}_{y_i}^{b_i}\right)\rho_i^{AB}],
\end{split}
\end{equation}

where $\lambda_{i}$ is the hidden variable, $\hat{M}_{x_i}^{a_i}$ and $\hat{M}_{y_i}^{b_i}$ are the projectors of  observables $\hat{A}_{x_i}$ and $\hat{B}_{y_i}$ with specific outcomes, respectively. The probability distributions satisfy the non-signaling condition, $\forall x_i,x_i',y_i,y_i',a_i,b_i,\lambda_{i}$,

\begin{equation}
\begin{split}
\sum_{b_i\in\{\pm1\}}\Pr(a_i,b_i|x_i,y_i,\lambda_{i}) &= \sum_{b_i\in\{\pm1\}}\Pr(a_i,b_i|x_i,y_i',\lambda_{i}), \\
\sum_{a_i\in\{\pm1\}}\Pr(a_i,b_i|x_i,y_i,\lambda_{i}) &= \sum_{a_i\in\{\pm1\}}\Pr(a_i,b_i|x_i',y_i,\lambda_{i}).
\end{split}
\end{equation}

The sequential setting imposes further restrictions, such that for all $j>i$ and any given values of $x_i,y_i,a_i,b_i,\lambda_{i}$ at time $i$ and $x_j,y_j,x_j',y_j'$ at time $j$,

\begin{equation}
\begin{split}
\sum_{a_j,b_j}\Pr(a_i,b_i,a_j,b_j|x_i,y_i,x_j,y_j,\lambda_{i}) = \sum_{a_j,b_j}\Pr(a_i,b_i,a_j,b_j|x_i,y_i,x_j',y_j',\lambda_{i}).
\end{split}
\end{equation}

For the convenience of constructing phase-error measurement, we present an equivalent description of the above sequential processing. The $n$ experimental rounds correspond to $2n$ subsystems of Alice and Bob. Initially, these subsystems can be arbitrarily entangled. There is no limit on their dimensions. The measurements, $\hat{A}_{x_i}\otimes\hat{B}_{y_i}$, in the $i$th round are carried out on Alice's and Bob's $i$th subsystems. In the equivalent picture, as shown in Figure <ref>, Alice and Bob's system evolves from the $i$th round to the $(i+1)$th round as follows.

* At the beginning of the $i$th round, the joint state of Alice's and Bob's subsystems is  $\rho_{i}^{AB}\in\mathcal{D}(\mathcal{H}_{A_i}\otimes\mathcal{H}_{B_i})$. Here, we use the same notations as the process of Figure <ref>, but we should understand $A_i$ and $B_i$ as subsystems.

* Alice and Bob perform the measurement, $\hat{A}_{x_i}\otimes\hat{B}_{y_i}$, on $\rho_{i}^{AB}$ and obtain outputs $a_i,b_i\in\{-1,1\}$. This is the same the process of Figure <ref>.

* The post-measurement state is transferred to the $(i+1)$th subsystems of Alice and Bob, which is done locally. We describe this `transfer' operation by a hidden updating quantum operation $\hat{K}_i^A$ acting on the $(i+1)$th subsystem of Alice as shown in Figure <ref>, and similarly on Bob's side. For instance, $\hat{K}_i^A$ can be realised via teleportation from the $i$th subsystem to the $(i+1)$th subsystem [Bennett et al., 1993]. After this step, the $i$th subsystems are discarded. In a way, one can think of relabeling the subsystems from $i$ to $i+1$.

* A general joint channel $\hat{T}_i$ is applied to the $i+1$ subsystems, after which the state becomes $\rho_{i+1}^{AB}\in\mathcal{D}(\mathcal{H}_{A_{i+1}}\otimes\mathcal{H}_{B_{i+1}})$ and is passed on to the $(i+1)$th round. This is the same the process of Figure <ref>.

[circle,fill,gray,inner sep=1pt,label=left:$\mathcal{H}_{A_i}$] (orig) at (0,0) ;
[rectangle,draw=black,fill=orange!10!white,minimum size=20pt,rounded corners] (K) at ($ (orig) + (1cm,0) $) $\hat{K}_{i-1}^A$;
[rectangle,fill=blue!10!white,minimum size=20pt,rounded corners] (TA) at ($ (K.east) + (1cm,0) $) $\hat{T}_{i-1}$;
(TA.south west) [rounded corners] – (TA.north west)  – (TA.north east) – (TA.south east);
[rectangle,draw=black,fill=green!10!white,minimum size=20pt,rounded corners] (Ax) at ($ (TA.east) + (1.5cm,0) $) $\hat{A}_{x_i}$;
[<-] (Ax.north) –++ (0,0.3) node[above]$x_i$;
[->] (Ax.east) –++ (.3,0) node[right] $a_i$;
(orig) – (K.west) (K.east) – (TA.west) (TA.east) – (Ax.west) node[midway,above] $\rho_i^A$;
[circle,fill,gray,inner sep=1pt,label=left:$\mathcal{H}_{A_{i+1}}$] (orig1) at (0,-1.5) ;
[rectangle,draw=black,fill=orange!10!white,minimum size=20pt,rounded corners] (K1) at ($ (Ax) + (0,-1.5cm) $) $\hat{K}_{i}^A$;
[rectangle,fill=blue!10!white,minimum size=20pt,rounded corners] (TA1) at ($ (K1.east) + (1cm,0) $) $\hat{T}_{i}$;
(TA1.south west) [rounded corners] – (TA1.north west)  – (TA1.north east) – (TA1.south east);
[rectangle,draw=black,fill=green!10!white,minimum size=20pt,rounded corners] (Ax1) at ($ (TA1.east) + (1.5cm,0) $) $\hat{A}_{x_{i+1}}$;
[<-] (Ax1.north) –++ (0,0.3) node[above]$x_{i+1}$;
[->] (Ax1.east) –++ (.3,0) node[right] $a_{i+1}$;
(orig1) – (K1.west) (K1.east) – (TA1.west) (TA1.east) – (Ax1.west) node[midway,above] $\rho_{i+1}^A$;
[snake=snake,gray,opacity=.5] (orig) – (orig1);
[-stealth,gray,opacity=.5] (Ax) – (K1.north);

The $i$th and $(i+1)$th subsystems on Alice's side in a sequential manner. Bob's side is similar. For the $i$th subsystem of Alice, input state $\rho_i^{A}$ is measured by observable $\hat{A}_{x_i}$. Alice obtains classical output $a_i$. A hidden updating quantum operation $\hat{K}_i^A$ transfers the post-measurement state from subsystem $i$ to subsystem $(i+1)$. Afterwards, Alice and Bob's devices can communicate with each other to perform a joint operation $\hat{T}_i$, only half of which is shown in the figure. As a result, the state of the $(i+1)$th subsystem becomes $\rho_{i+1}^A$. We emphasise that before measurement, correlation or entanglement may already exist over the subsystems.

We remark that we do not impose any restriction on the initial joint state of Alice and Bob and operations $\hat{K}_i^A,\hat{T}_i$ in this description. The key point is that for any possible sequential system evolution in Figure <ref>, one can find an equivalent description in the manner of Figure <ref>.

§.§ Effective system dimension reduction

In the estimation of the raw key's privacy, we shall use the measurements $\hat{A}_0,\hat{A}_1$ and $\hat{B}_0,\hat{B}_1$ in each round. We can take advantage of Jordan's Lemma to effectively reduce the system dimension [Tsirelson, 1993]. We restate the proof given in Ref. [Pironio et al., 2009].

For two Hermitian operators $\hat{A}_0,\hat{A}_1$ with eigenvalues $\pm1$ that act on the same Hilbert space $\mathcal{H}$ with an at most countable dimension, there exists a direct sum decomposition $\mathcal{H}=\bigoplus_\alpha\mathcal{H}^\alpha$ such that $\hat{A}_0,\hat{A}_1$ are simultaneously block diagonal, $\hat{A}_0 = \bigoplus_\alpha \hat{A}_0^\alpha,\,\hat{A}_1 = \bigoplus_\alpha \hat{A}_1^\alpha,\,\hat{A}_0^\alpha,\hat{A}_1^\alpha\in\mathcal{L}(\mathcal{H}^\alpha)$, and $\forall\alpha,\dim\mathcal{H}^\alpha\leq 2$.

Since the binary observables $\hat{A}_0,\hat{A}_1\in\mathcal{L}(\mathcal{H})$ have eigenvalues $\pm1$, they are unitary operators and do not have zero eigenspaces. The operator $\hat{A}_1\hat{A}_0$ is also unitary, and hence there exists a vector $\ket{\alpha}$, such that

\begin{equation}
\hat{A}_1\hat{A}_0\ket{\alpha} = a_{\alpha}\ket{\alpha},
\end{equation}

with $a_{\alpha}\in\mathbb{C}$ and $|a_{\alpha}| = 1$. Then we have

\begin{equation}
\hat{A}_1\hat{A}_0(\hat{A}_1\ket{\alpha}) = a_{\alpha}^*(\hat{A}_1\ket{\alpha}),
\end{equation}

indicating that $\ket{\alpha'}\equiv\hat{A}_1\ket{\alpha}$ is also an eigenvector of $\hat{A}_1\hat{A}_0$. Consider a subspace $\mathcal{H}^\alpha=\text{span}(\ket{\alpha},\ket{\alpha'})\subseteq \mathcal{H}$, if $\abs{\braket{\alpha}{\alpha'}}=1$, then $\dim{\mathcal{H}^\alpha}=1$; otherwise, $\dim{\mathcal{H}^\alpha}=2$.
Since $\hat{A}_1\hat{A}_0$ is unitary, its eigenvectors span the whole Hilbert space. Then, we can iterate above steps and finally decompose the Hilbert space, $\mathcal{H}=\oplus_{\alpha}\mathcal{H}^\alpha$, where $\alpha$ denotes the index of subspace.

Next, we verify that $\mathcal{H}^\alpha$ are invariant subspaces of the operators $\hat{A}_0,\hat{A}_1$,

\begin{equation}
\begin{split}
\hat{A}_1\ket{\alpha}&=\ket{\alpha'}, \\
\hat{A}_1\ket{\alpha'}&=\ket{\alpha}, \\
\hat{A}_0\ket{\alpha'}&=\hat{A}_0\hat{A}_1\ket{\alpha}=(\hat{A}_1\hat{A}_0)^{\dagger}\ket{\alpha}=a_{\alpha}^*\ket{\alpha}, \\
\hat{A}_0\ket{\alpha}&=\hat{A}_0\hat{A}_1\hat{A}_1\ket{\alpha}=(\hat{A}_1\hat{A}_0)^{\dagger}\ket{\alpha'}=a_{\alpha}\ket{\alpha'}. \\
\end{split}
\end{equation}

Therefore, the lemma is proved.

As a consequence of Jordan's lemma, on Alice's side, there exists a direct-sum decomposition of the space $\mathcal{H}_A=\bigoplus_\alpha\mathcal{H}_A^\alpha$ and $\forall\alpha, \dim{\mathcal{H}_A^\alpha}\le2$, such that the  quantum observables $\hat{A}_0,\hat{A}_1$ can be expressed as

\begin{equation}
\hat{A}_i=\bigoplus_\alpha \hat{A}_i^\alpha=\sum_\alpha\hat{\Pi}_\alpha \hat{A}_i\hat{\Pi}_\alpha,
\end{equation}

where $i\in\{0,1\}$ and $\hat{\Pi}_\alpha$ is the projector onto the subspace $\mathcal{H}_A^\alpha$. The expectation of measuring the observable on the system $\rho^A$ becomes

\begin{equation}
\begin{split}
\Tr(\hat{A}_i\rho^A) &= \sum_\alpha p_\alpha^A\Tr(\hat{A}_i^\alpha\rho_\alpha^A), \\
\end{split}
\end{equation}

where $\rho^A_\alpha\in\mathcal{D}(\mathcal{H}_A^\alpha)$, $p^A_\alpha\ge0$, $\sum_\alpha p^A_\alpha=1$, and

\begin{equation}
\begin{split}
\sum_\alpha\hat{\Pi}_\alpha\rho^A\hat{\Pi}_\alpha &=\bigoplus_\alpha p^A_\alpha\rho^A_\alpha. \\
\end{split}
\end{equation}

Since $\dim{\mathcal{H}_A^\alpha}\le2$, we can effectively treat $\rho^A_\alpha$ as a qubit state.

A similar argument can be applied on Bob's side, where $\mathcal{H}_B=\bigoplus_\beta\mathcal{H}_B^\beta$. Therefore, the effective system of Alice and Bob in a round can be treated as a mixture of 2-qubit states, $\rho_{\alpha\beta}^{AB}\in\mathcal{D}(\mathcal{H}_A^\alpha\otimes\mathcal{H}_B^\beta)$. In DIQKD, we can absorb the variables, $\alpha$ and $\beta$, into the hidden variable $\lambda$. That is, given $\lambda$, 2-qubit state $\rho_{\lambda}^{AB}$, and Alice's and Bob's observables $\hat{A}_0^\lambda,\hat{A}_1^\lambda,\hat{B}_0^\lambda,\hat{B}_1^\lambda$ are fixed. So, we can also treat $\lambda$ as a system variable.

Note that the additional measurement setting on Alice's side, $\hat{A}_2$, cannot be guaranteed to take the block-diagonal form with the same direct-sum decomposition of the Hilbert space $\mathcal{H}_A$ as $\hat{A}_0,\hat{A}_1$. Nevertheless, we can further absorb the parameters for constructing the measurement $\hat{A}_2$ into $\lambda$,  $\hat{A}_2^{\lambda}$. In general, $\hat{A}_2^{\lambda}$ does not represent a qubit measurement on a qubit state. In the end, the system variable $\lambda$ would determine all the underlying states and  measurements.

In summary, the DIQKD protocol can be equivalently modelled by the quantum circuit shown in Figure <ref>. We summarise the system modelling results with the equivalent process description shown in Box <ref>, which generates the same classical statistics and quantum signals as the actual protocol. In this equivalent process description, it becomes clear how we should link the DIQKD security analysis to the complementarity-based security statement in Lemma <ref>. In the key generation rounds, the projection operations $\{\hat{\Pi}_{\lambda_i}^B\}_{\lambda_i}$ prepare Bob's subsystems in the key generation rounds to qubit ones, corresponding to Step 2 in the protocol of Box <ref> and naturally sufficing the state preparation requirement in Lemma <ref>.

[label=box:VirtualProtocol]Equivalent Process Description in DIQKD
Note: The process described here is an equivalent description of the physical process in Step 1, Box <ref>.

* State Preparation:

* Alice and Bob share a bipartite quantum state $\rho^{AB}\in \mathcal{D}\left\{\bigotimes_{i=1}^n[\mathcal{H}_{A(i)}\otimes\mathcal{H}_{B(i)}]\right\}$.

* Quantum channels $\hat{K}_i^A,\hat{K}_i^B$ are applied to the $i$th subsystems $\mathcal{H}_{A(i)},\mathcal{H}_{B(i)}$ based on all the local information.

* An LOCC channel $\hat{T}_{i}$ is applied to the $(i+1)$th subsystems between $\mathcal{H}_{A(i+1)},\mathcal{H}_{B(i+1)}$.

* Projection to Qubits:

* If $x_i = 2$,

The projection $\{\hat{\Pi}_{\lambda_i}^B\}_{\lambda_i}$ is applied to Bob's $i$th subsystem. The projection result of $\lambda_i$ is recorded.

* If $x_i = 0,1$,

The projection $\{\hat{\Pi}_{\lambda_i}^A\otimes\hat{\Pi}_{\lambda_i}^B\}_{\lambda_i}$ is applied to Alice's and Bob's $i$th subsystems. The projection result of $\lambda_i$ is recorded.

* Measurements:

* If $x_i = 2$,

Alice and Bob measure $\hat{A}_{2}^{\lambda_i},\,\hat{B}_{y}^{\lambda_i}$ on their $i$th subsystems respectively, where $y_i = y$.

* If $x_i = 0,1$,

Alice and Bob measure $\hat{A}_{x}^{\lambda_i},\,\hat{B}_{y}^{\lambda_i}$ on their $i$th subsystems respectively, where $x_i = x,y_i = y$.

[circle,fill,gray,inner sep=1pt,label=left:$\mathcal{H}_{A_i}$] (orig) at (0,0) ;
[rectangle,draw=black,fill=orange!10!white,minimum size=20pt,rounded corners] (K) at ($ (orig) + (1cm,0) $) $\hat{K}_{i-1}^A$;
[rectangle,fill=blue!10!white,minimum size=20pt,rounded corners] (TA) at ($ (K.east) + (1cm,0) $) $\hat{T}_{i-1}$;
(TA.south west) [rounded corners] – (TA.north west)  – (TA.north east) – (TA.south east);
[rectangle,draw=black,fill=green!10!white,minimum size=20pt,rounded corners] (Ax) at ($ (TA.east) + (1.5cm,0) $) $\hat{A}_{x_i}$;
[<-] (Ax.north) –++ (0,0.3) node[above]$x_i$;
[->] (Ax.east) –++ (.3,0) node[right] $a_i$;
(orig) – (K.west) (K.east) – (TA.west) (TA.east) – (Ax.west) node[midway,above] $\rho_i^A$;

[circle,fill,gray,inner sep=1pt,label=left:$\mathcal{H}_{B_i}$] (origB) at (0,-1.5) ;
[rectangle,draw=black,fill=orange!10!white,minimum size=20pt,rounded corners] (KB) at ($ (origB) + (1cm,0) $) $\hat{K}_{i-1}^B$;
[rectangle,fill=blue!10!white,minimum size=20pt,rounded corners] (TB) at ($ (KB.east) + (1cm,0) $) $\hat{T}_{i-1}$;
[rectangle,draw=black,fill=green!10!white,minimum size=20pt,rounded corners] (Bx) at ($ (TB.east) + (1.5cm,0) $) $\hat{B}_{y_i}$;
[<-] (Bx.north) –++ (0,0.3) node[above]$y_i$;
[->] (Bx.east) –++ (.3,0) node[right] $b_i$;
(origB) – (KB.west) (KB.east) – (TB.west) (TB.east) – (Bx.west) node[midway,above] $\rho_i^B$;

[black,fill=blue!10!white,rounded corners] (TA.north west) rectangle node$\hat{T}_{i-1}$ (TB.south east) ;

[circle,fill,gray,inner sep=1pt,label=left:$\mathcal{H}_{A_{i+1}}$] (orig1) at (0,-3) ;
[rectangle,draw=black,fill=orange!10!white,minimum size=20pt,rounded corners] (K1) at ($ (Ax) + (0,-3cm) $) $\hat{K}_{i}^A$;
[rectangle,fill=blue!10!white,minimum size=20pt,rounded corners] (TA1) at ($ (K1.east) + (1cm,0) $) $\hat{T}_{i}$;
(TA1.south west) [rounded corners] – (TA1.north west)  – (TA1.north east) – (TA1.south east);
[rectangle,draw=black,fill=green!10!white,minimum size=20pt,rounded corners] (Ax1) at ($ (TA1.east) + (1.5cm,0) $) $\hat{A}_{x_{i+1}}$;
[<-] (Ax1.north) –++ (0,0.3) node[above]$x_{i+1}$;
[->] (Ax1.east) –++ (.3,0) node[right] $a_{i+1}$;
(orig1) – (K1.west) (K1.east) – (TA1.west) (TA1.east) – (Ax1.west) node[midway,above] $\rho_{i+1}^A$;

[circle,fill,gray,inner sep=1pt,label=left:$\mathcal{H}_{B_{i+1}}$] (origB1) at (0,-4.5) ;
[rectangle,draw=black,fill=orange!10!white,minimum size=20pt,rounded corners] (KB1) at ($ (Bx) + (0,-3cm) $) $\hat{K}_{i}^B$;
[rectangle,fill=blue!10!white,minimum size=20pt,rounded corners] (TB1) at ($ (KB1.east) + (1cm,0) $) $\hat{T}_{i}$;

[rectangle,draw=black,fill=green!10!white,minimum size=20pt,rounded corners] (Bx1) at ($ (TB1.east) + (1.5cm,0) $) $\hat{B}_{y_{i+1}}$;
[<-] (Bx1.north) –++ (0,0.3) node[above]$y_{i+1}$;
[->] (Bx1.east) –++ (.3,0) node[right] $a_{i+1}$;
(origB1) – (KB1.west) (KB1.east) – (TB1.west) (TB1.east) – (Bx1.west) node[midway,above] $\rho_{i+1}^B$;

[black,fill=blue!10!white,rounded corners] (TA1.north west) rectangle node$\hat{T}_{i}$ (TB1.south east) ;

[snake=snake,gray,opacity=.5] (orig) – (origB1);

System characterisation of the sequential setting. Two rounds are depicted for demonstration.

The subsystems for each round are denoted by their Hilbert spaces $\mathcal{H}_{A_i},\mathcal{H}_{B_i}$,

which are measured in a time sequence.

In general, the subsystems can be correlated or entangled a priori, as shown by the curvy line.
In each round, Alice and Bob randomly set the measurement bases $x_i,y_i$, respectively. The measurement on either party is independent of the other but can be influenced by all previous events on both sides.
After the measurements in a round end, the leftover quantum systems are transferred to the next subsystems of Alice and Bob via local hidden updating quantum operations $\hat{K}_i^A,\hat{K}_i^B$, respectively.

Afterwards, a general quantum channel $\hat{T}_i$ is applied to Alice's and Bob's systems, which prepares the joint system to be measured in the subsequent round in $\rho_{i+1}^{AB}$ and allows the untrusted devices to synchronise the history on both sides. For measurements corresponding to the settings $x_i,y_i\in\{0,1\}$, they can be described by qubit observables realised via the qubit projections $\hat{\Pi}_{\lambda_i}^A,\hat{\Pi}_{\lambda_i}^B$.

§ SINGLE-ROUND PHASE-ERROR PROBABILITY

§.§ Problem as an optimisation

In this section, we shall derive the phase-error probability formula in a single round. Comparing to the virtual protocol in Box <ref>, the analysis in this section shall give the construction of the auxiliary measurement, $\hat{M}_R$. Along the complementarity-based quantum-error-correction approach, we virtually replace the key generation measurements with the phase-error measurement shown in Box <ref> and remain all the other operations (both quantum and classical) the same as in the original protocol. Here, $\hat{B}_{\bot}^{\lambda_i}\in\mathcal{L}(\mathcal{H}_B^{\lambda_i})$ is the complementary observable of $\hat{B}_0^{\lambda_i}\in\mathcal{L}(\mathcal{H}_B^{\lambda_i})$. We denote the eigenvectors of $\hat{B}_{\bot}^{\lambda_i}$ as $\ket{b_{\bot}^{\lambda_i(+)}},\ket{b_{\bot}^{\lambda_i(-)}}$ and the eigenvectors of $\hat{B}_{0}^{\lambda_i}$ as $\ket{b_{0}^{\lambda_i(+)}},\ket{b_{0}^{\lambda_i(-)}}$. The sets of eigenvectors form mutually unbiased bases. Since the observables are now qubit ones, their eigenvectors satisfy

\begin{equation}
\left|\bra{b_{\bot}^{\lambda_i(s)}}\ket{b_{0}^{\lambda_i(t)}}\right|^2=\frac{1}{2},\forall s,t\in\{+,-\}.
\end{equation}

The measurement on Alice's side, $\hat{A}_{\theta_i}^{\lambda_i}\in\mathcal{L}(\mathcal{H}_A^{\lambda_i})$, is an auxiliary measurement. Without loss of generality, we can take it as a binary projection measurement with eigenvalues $\pm1$. The parameter $\theta_i$ denotes the freedom in the choice of the auxiliary measurement. The explicit parameterised representation of $\hat{A}_{\theta_i}^{\lambda_i}$ shall be made clear in the next section. In the prediction, Alice takes the measurement result of $\hat{A}_{\theta_i}^{\lambda_i}$ as her guess of the outcome of $\hat{B}_{\bot}^{\lambda_i}$. With probability $[1+\alpha(\hat{A}_{\theta_i}^{\lambda_i})]/2$, the outcome of $\hat{B}_\bot^{\lambda_i}$ can be predicted correctly, where

\begin{equation}\label{Eq:ComBasis}
\alpha(\hat{A}_{\theta_i}^{\lambda_i}) = \Tr[\rho_{\lambda_i}^{AB}({\hat{A}_{\theta_i}^{\lambda_i}}\otimes \hat{B}_\bot^{\lambda_i})],
\end{equation}

which we call the correlation between the measurements $\hat{A}_{\theta_i}^{\lambda_i}$ and $\hat{B}_\bot^{\lambda_i}$ on the state $\rho_{\lambda_i}^{AB}$. If the measurement results of $\hat{B}_{\bot}^{\lambda_i}$ and $\hat{A}_{\theta_i}^{\lambda_i}$ are perfectly correlated, that is, $\alpha(\hat{A}_{\theta_i}^{\lambda_i})=1$, the system would be certified on the complementary basis. In this case, the key bit $\kappa_i^B$ shall be private. In a general case, we introduce a random variable $E_{p}^{\lambda_i}$, which we call the phase-error variable in the $i$th round. An error occurs if the measurement results of $\hat{A}_{\theta_i}^{\lambda_i}$ and $\hat{B}_{\bot}^{\lambda_i}$ are not equal and $E_{p}^{\lambda_i}=1$, otherwise $E_{p}^{\lambda_i}=0$. Conditioned on the system variable, had the phase-error measurement been performed in the $i$th round, a phase error would occur with probability

\begin{equation}\label{def:ConPhaseError}
\Pr{E_{p}^{\lambda_i} = 1|x_i = 2, y_i = 0, \lambda_i} = \dfrac{1-\alpha(\hat{A}_{\theta_i}^{\lambda_i})}{2}.
\end{equation}

In Figure <ref>, we depict the virtual phase-error measurement procedure. If we compare it to the well-known Bennett-Brassard-1984 QKD protocol [Bennett and Brassard, 1984], $\hat{A}_{2}^{\lambda_i}$ and $\hat{B}_0^{\lambda_i}$ correspond to the $Z$-basis measurements, while $\hat{A}_{\theta_i}^{\lambda_i}$ and $\hat{B}_{\perp}^{\lambda_i}$ correspond to the $X$-basis measurements.

[label=box:PhaseError]Phase-error Measurement

* Replace only the key generation measurements with the following operations.

* The information exchange with the outside needs to be the same as in the experiment.

* Alice applies the projection $\{\hat{\Pi}_{\lambda_i}^A\}_{\lambda_i}$ to her $i$th subsystem.

* Alice and Bob measure $\hat{A}_{\theta_i}^{\lambda_i},\hat{B}_{\bot}^{\lambda_i}$ on their systems and record the measurement results, respectively.

* Based on the measurement outcome of $\hat{A}_{\theta_i}^{\lambda_i}$, Alice predicts the corresponding measurement outcome of $\hat{B}_{\bot}^{\lambda_i}$.

* Alice and Bob compare the measurement results. If Alice makes a wrong prediction, a phase error occurs with a binary variable $E_{p}^{\lambda_i}$ taking the value $1$. Otherwise, $E_{p}^{\lambda_i}=0$.

A schematic diagram of the virtual phase-error measurement. The underlying quantum state $\rho_{\lambda_i}^{AB}$ depends on the system variable $\Lambda_i$. (a) In a key generation round, the key bit $\kappa_i^B$ is obtained by measuring $\hat{B}_0^{\lambda_i}$ on the state $\rho_{\lambda_i}^B$. (b) In a virtual phase-error measurement, Alice measures $\hat{A}_{\theta_i}^{\lambda_i}$ on her subsystem $\rho_{\lambda_i}^A$. Bob measures $\hat{B}_{\bot}^{\lambda_i}$ on his subsystem $\rho_{\lambda_i}^B$, where $\hat{B}_{\bot}^{\lambda_i}$ is complementary to $\hat{B}_{0}^{\lambda_i}$. Alice takes the measurement result of $\hat{A}_{\theta_i}^{\lambda_i}$ to predict the result of $\hat{B}_{\perp}^{\lambda_i}$.

By our definition of the system variable $\lambda_i$ (see Sec. <ref>), the correlated effects brought by the previous rounds have been considered.

We denote the corresponding underlying phase-error probability corresponding to the system variable value $\lambda_i$ in Eq. (<ref>) as $e_p^{\lambda_i}$. In this section, all the conditional probabilities should be considered as a value, where the terms being conditioned are specific values of random variables.

While the phase error is not directly measured in the protocol, the phase-error probability is an intrinsic property of the system. Intuitively, more entanglement between Alice and Bob implies more privacy in the generated key and hence the smaller the phase-error probability. On the other hand, entanglement can be quantified via the expected Bell value. Conditioned on the system variable, the expected Bell value of a round is given by

\begin{equation}\label{def:UnderBellValue}
\begin{split}
S^{\lambda_i} &\equiv
\sum_{x,y\in\{0,1\}}(-1)^{xy}\mathbb{E}(a_{i}b_{i}|x_i=x,y_i=y, \lambda_i) \\ &=
\sum_{x,y\in\{0,1\}}(-1)^{xy}\Tr[\rho_{\lambda_i}^{AB}(\hat{A}_{x}^{\lambda_i}\otimes \hat{B}_{y}^{\lambda_i})] \\ &= \Tr(\rho_{\lambda_i}^{AB}\hat{S}^{\lambda_i}).
\end{split}
\end{equation}

Here, the operator

\begin{equation}\label{Eq:BellOperator}
\hat{S}^{\lambda_i}=\sum_{x,y\in\{0,1\}}(-1)^{xy}\hat{A}_{x}^{\lambda_i}\otimes \hat{B}_{y}^{\lambda_i}
\end{equation}

is the Bell operator of the round given the system variable value $\lambda_i$.

For brevity, we omit the system variable $\lambda$ and the label for round number in this section, and express the joint underlying quantum system in the round as $\rho\in\mathcal{D}(\mathcal{H}_A\otimes\mathcal{H}_B)$. Suppose given the system variable, the expected Bell value $S$ of the round is given. To obtain the worst phase-error probability under this constraint, we can solve the following optimisation problem of the correlation between $\hat{A}_\theta,\hat{B}_\perp$ on the state $\rho$,

\begin{equation}\label{Eq:OriginOpt}
\begin{split}
\alpha =& \min_{\rho,\hat{A}_0,\hat{A}_1,\hat{B}_0,\hat{B}_1}\max_{\hat{A}_\theta}\Tr[\rho({\hat{A}_\theta}\otimes \hat{B}_\perp)], \\
\text{s.t. }
&S = \sum_{x,y\in\{0,1\}}(-1)^{xy}\Tr[\rho(\hat{A}_x\otimes \hat{B}_y)].
\end{split}
\end{equation}

All the measurement observables are projective with eigenvalues $\pm1$, and $\hat{A}_0,\hat{A}_1,\hat{A}_{\theta}\in\mathcal{L}(\mathcal{H}_A),\hat{B}_0,\hat{B}_1,\hat{B}_\perp\in\mathcal{L}(\mathcal{H}_B)$. For convenience, we first state the optimisation result,

The solution to the optimisation in Eq. (<ref>) is given by,

\begin{eqnarray}\label{SuppEq:PhaseErrorProb}
\alpha\geq\alpha(S)\equiv
\left\{
\begin{tabular}{ll}
$\sqrt{(S/2)^2-1}$, & $2<S\leq2\sqrt{2}$,\\
$0$, & $S\leq2$.
\end{tabular}
\right.
\end{eqnarray}

Therefore, the corresponding phase-error probability is upper bounded by

\begin{eqnarray}\label{Eq:SuppPhaseError}
e_p\leq e_p(S)\equiv\dfrac{1-\alpha(S)}{2}=
\left\{
\begin{tabular}{ll}
$\dfrac{1-\sqrt{(S/2)^2-1}}{2}$, & $2<S\leq2\sqrt{2}$,\\
$\dfrac{1}{2}$, & $S\leq2$.
\end{tabular}
\right.
\end{eqnarray}

If we restrict Eve's hacking strategy to i.i.d. attacks, where the system variables $\Lambda_i$ are independent of $i$, the lemma is consistent with the previous result [Pironio et al., 2009]. Nevertheless, the result in Ref. [Pironio et al., 2009] has a different operational meaning as Holevo information and takes a different approach. To our best knowledge, in the sense of phase-error probability, the first attempt to construct a complementarity-based device-independent security analysis starts in Ref. [Tsurumaru and Ichikawa, 2016], where the authors make the same definition for a complementary basis as in Eq. (<ref>). Yet the authors did not reach a tight relation between phase-error probability and expected Bell value. Upon finishing our paper, we notice the work of Ref. [Woodhead et al., 2021], which arrives at a similar result as ours in a single round with a slightly different derivation. However, the work does not further go into the non-i.i.d. statistics. Instead, to obtain a full security analysis, the authors transform the result to the quantum entropy conditioned on Eve's system via the entropic uncertainty relation [Berta et al., 2010] and resorts to the entropic approach in the end [Arnon-Friedman et al., 2018].

We solve the optimisation problem in two steps. In the first step, we parameterise the quantum system and operators using Pauli operators. Afterwards, we derive a lower bound on the optimal value of the optimisation in Eq. (<ref>) from the dual problem.

§.§ Step 1: operator parametrisation

Without loss of generality, the observables can be taken as expanded by the Pauli operators $\hat{\sigma}_x,\hat{\sigma}_z$ on the corresponding spaces by using additional degrees of freedom. The measurements can be parameterised as

\begin{equation}\label{Eq:EffMeasure}
\begin{split}
&\hat{A}_0 = \sin{\theta_0}\hat{\sigma}_x + \cos{\theta_0}\hat{\sigma}_z, \\
&\hat{A}_1 = \sin{\theta_1}\hat{\sigma}_x + \cos{\theta_1}\hat{\sigma}_z, \\
&\hat{B}_0 = \hat{\sigma}_z, \\
&\hat{B}_1 = \sin{\gamma}\hat{\sigma}_x + \cos{\gamma}\hat{\sigma}_z. \\
\end{split}
\end{equation}

The complementary measurement of $\hat{B}_0$, $\hat{B}_\perp$, and the auxiliary measurement observable on Alice's side, $\hat{A}_\theta$, can also be spanned by $\hat{\sigma}_x,\,\hat{\sigma}_z$,

\begin{equation}
\begin{split}
\hat{A}_\theta &= \sin{\theta}\hat{\sigma}_x+\cos{\theta}\hat{\sigma}_z, \\
\hat{B}_\perp &= \hat{\sigma}_x.
\end{split}
\end{equation}

Since we are focused on the measurement results of the observables, where the system $\rho$ and its complex conjugate $\rho^*$ give the same statistics, the density operator of the shared state $\rho$ can be taken as real positive semi-definite. We can write the density operator of $\rho$ as the matrix

\begin{equation}\label{SuppEq:state}
\rho=
\left(\begin{matrix}
\rho_{11} & \rho_{12} & \rho_{13} & \rho_{14}\\
\rho_{21} & \rho_{22} & \rho_{23} & \rho_{24}\\
\rho_{31} & \rho_{32} & \rho_{33} & \rho_{34}\\
\rho_{41} & \rho_{42} & \rho_{43} & \rho_{44}
\end{matrix}\right)
\end{equation}

under the Bell-state basis $\left\{\ket{\Phi^+},\ket{\Psi^-},\ket{\Phi^-},\ket{\Psi^+}\right\}$, with $\rho_{ij}=\rho_{ji},\forall i,j\in\{1,2,3,4\}$. The Bell states are expressed as

\begin{equation}
\begin{split}
\ket{\Phi^+}&=\frac{\ket{00}+\ket{11}}{\sqrt{2}},\\ \ket{\Psi^-}&=\frac{\ket{01}-\ket{10}}{\sqrt{2}},\\ \ket{\Phi^-}&=\frac{\ket{00}-\ket{11}}{\sqrt{2}},\\ \ket{\Psi^+}&=\frac{\ket{01}+\ket{10}}{\sqrt{2}},
\end{split}
\end{equation}

where $\{\ket{0},\ket{1}\}$ are the eigenvectors of the Pauli operator $\hat{\sigma}_z$ acting on the corresponding local system. We denote $c_{ij}=\Tr\left[\rho (\hat{\sigma}_i\otimes\hat{\sigma}_j)\right],\forall i,j\in\{x,z\}$. After some simple calculation, we could get

\begin{equation}\label{SuppEq:correlation}
\begin{split}
\end{split}
\end{equation}

The value of the objective function becomes

\begin{equation}
\Tr\left[\rho (\hat{A}_\theta\otimes\hat{B}_\perp)\right]=\sin{\theta}c_{xx} + \cos{\theta}c_{zx}.
\end{equation}

We note that the objective function has a trivial lower bound of zero. In the optimisation of the objective function, the minimisation and the maximisation can be exchanged. Now we focus on the optimisation over $\hat{A}_{\theta}$. If $c_{xx}=c_{zx}=0$, the objective function is zero. If $c_{xx},c_{zx}$ do not simultaneously take the value of zero, say $c_{xx}\neq0$, then by taking $\theta=\arctan{-\frac{c_{zx}}{c_{xx}}}$, the objective function takes the value of zero. Therefore, we have $e_p\leq\frac{1}{2}$. Intuitively, this means that Alice can always find a strategy such that her prediction is correct with a probability of at least $1/2$.

For the case where $c_{xx},c_{zx}$ do not simultaneously take the value of zero, over the optimisation of $\hat{A}_\theta$, the optimum value of the objective function is taken when

\begin{equation}
\begin{split}
\sin{\theta}&=\frac{|c_{xx}|}{\sqrt{c_{xx}^2+c_{zx}^2}},\\
\cos{\theta}&=\frac{|c_{zx}|}{\sqrt{c_{xx}^2+c_{zx}^2}}.
\end{split}
\end{equation}

The optimisation problem becomes

\begin{equation}\label{SuppEq:primal}
\begin{split}
\alpha &= \min_{\rho_{ij},\theta_0,\theta_1,\gamma}\sqrt{c_{xx}^2+c_{zx}^2}, \\
\text{s.t. }
S &= S(\rho_{ij},\theta_0,\theta_1,\gamma) = \sum_{x,y\in\{0,1\}}(-1)^{xy}\Tr[\rho(\hat{A}_x\otimes \hat{B}_y)].
\end{split}
\end{equation}

The case of $c_{xx}=c_{zx}=0$ can be unified to Eq. (<ref>). The function $S(\rho_{ij},\theta_0,\theta_1,\gamma)$ represents the expected Bell value given by the shared state with elements in the density matrix $\rho_{ij}$, and measurement observables parameterised by $\theta_0,\theta_1,\gamma$. We consider a unitary operator $\hat{R}(\vartheta)=\cos{\frac{\vartheta}{2}}\hat{I}+i\sin{\frac{\vartheta}{2}}\hat{\sigma}_y$ acting on $\mathcal{H}_A$. By applying the unitary operation of $\left(\hat{R}(\vartheta)\otimes\hat{I}\right)[\cdot]\left(\hat{R}(\vartheta)\otimes\hat{I}\right)^{-1}$ to both $\rho$ and $\hat{A}_x\otimes\hat{B}_y$, the solution to the optimization does not change. A simple computation shows

\begin{equation}
\begin{split}
\left(R(\vartheta)\otimes\hat{I}\right)\rho\left(R(\vartheta)\otimes\hat{I}\right)^{-1}=\left(\begin{matrix}\rho'_{11} & \rho'_{12} & \rho'_{13} & \rho'_{14}\\
\rho'_{21} & \rho'_{22} & \rho'_{23} & \rho'_{24}\\
\rho'_{31} & \rho'_{32} & \rho'_{33} & \rho'_{34}\\
\rho'_{41} & \rho'_{42} & \rho'_{43} & \rho'_{44}\end{matrix}\right),
\end{split}
\end{equation}

\begin{equation}
\begin{split}
\rho'_{12}&=\frac{1}{2}\left(\sin{\vartheta}\rho_{11}+2\cos{\vartheta}\rho_{12}-\sin{\vartheta}\rho_{22}\right),\\
\rho'_{34}&=\frac{1}{2}\left(-\sin{\vartheta}\rho_{33}+2\cos{\vartheta}\rho_{34}+\sin{\vartheta}\rho_{44}\right).
\end{split}
\end{equation}

Let $\vartheta = \arctan\left(\frac{-2\rho_{12}-2\rho_{34}}{\rho_{11}-\rho_{22}-\rho_{33}+\rho_{44}}\right)$. Then we have $c'_{zx}=\rho'_{12}+\rho'_{21}+\rho'_{34}+\rho'_{43}=0$. For simplicity, we still represent the measurements using the notations in Eq. (<ref>). The state can be parameterised as

\begin{equation}\label{Eq:EffState}
\begin{split}
\rho=
\left(\begin{matrix}
\rho_{11} & \rho_{12} & \rho_{13} & \rho_{14}\\
\rho_{12} & \rho_{22} & \rho_{23} & \rho_{24}\\
\rho_{13} & \rho_{23} & \rho_{33} & -\rho_{12}\\
\rho_{14} & \rho_{24} & -\rho_{12} & \rho_{44}
\end{matrix}\right),
\end{split}
\end{equation}

where $\sum_{i=1}\rho_{ii}^{\lambda}=1,\rho_{ij}\geq0$. In this parametrisation, $c_{zx}=0$. Then, the optimisation problem in Eq. (<ref>) can be simplified,

\begin{equation}\label{SuppEq:SimPrimal}
\begin{split}
\alpha &= \min_{\rho_{ij},\theta_0,\theta_1,\gamma}\left|c_{xx}\right|, \\
\text{s.t. }
S &= S(\rho_{ij},\theta_0,\theta_1,\gamma).
\end{split}
\end{equation}

Here, the function $S(\rho_{ij},\theta_0,\theta_1,\gamma)$ is parameterised by

\begin{eqnarray}
\left(\cos{\theta_0}+\cos{\theta_0}\cos{\gamma}+\cos{\theta_1}-\cos{\theta_1}\cos{\gamma}\right)c_{zz}
+ \left(\sin{\theta_0}\sin{\gamma}-\sin{\theta_1}\sin{\gamma}\right)c_{xx} \notag\\ && + \left(\sin{\theta_0}+\sin{\theta_0}\cos{\gamma}+\sin{\theta_1}-\sin{\theta_1}\cos{\gamma}\right)c_{xz}.
\end{eqnarray}

§.§ Step 2: lower bound from the dual problem

If we consider the dual problem of Eq. (<ref>),

\begin{equation}\label{SuppEq:dual}
\begin{split}
S^* &= \max_{\rho_{ij},\theta_0,\theta_1,\gamma}S(\rho_{ij},\theta_0,\theta_1,\gamma), \\
\text{s.t. }
\alpha&=|c_{xx}|,
\end{split}
\end{equation}

to which the solution is of the form $S^*(\alpha)$, with a duality argument, we can get a lower bound on the solution to the primal problem by taking the value $S$ into the inverse function $[S^*(\alpha)]^{-1}$. For the dual problem, the solution is given by Lemma <ref>. In the proof of the lemma, we employ the following observation.

The parameters defined in Eq. (<ref>) satisfy the following inequality

\begin{equation}\label{eq:cxzczz}
\begin{split}
\end{split}
\end{equation}

\begin{equation}
\begin{split}
|c_{xz}|&=|-\rho_{12}-\rho_{21}+\rho_{34}+\rho_{43}| \\
&\leq 2|\rho_{12}|+2|\rho_{34}| \\
&\leq 2\sqrt{\rho_{11}\rho_{22}} + 2\sqrt{\rho_{33}\rho_{44}} \\
&\leq 2\sqrt{(\rho_{11}+\rho_{33})(\rho_{22}+\rho_{44})} \\
&= 2\sqrt{\left(\frac{1+c_{zz}}{2}\right)\left(\frac{1-c_{zz}}{2}\right)} \\
&= \sqrt{1-c^2_{zz}}.
\end{split}
\end{equation}

In the second line, we have used the fact that the state $\rho$ in Eq. (<ref>) is Hermitian and the triangle inequality. In the third line, we have used the fact that $\rho$ is positive semi-definite. In the fourth line, we have used the Cauchy-Schwarz inequality. In the fifth line, we have used the expression of $c_{zz}$ in Eq. (<ref>) and the fact that $\Tr(\rho)=1$. Rearranging this inequality shall we obtain Eq. (<ref>).

The solution to Eq. (<ref>) is given by

\begin{equation}
S^*= 2\sqrt{1+\alpha^2}.
\end{equation}

From the Cauchy inequality, the value of $S(\rho_{ij},\theta_0,\theta_1,\gamma)$ can be upper bounded by

\begin{eqnarray}\label{SuppEq:Sbound}
&\leq&\sqrt{\left(c_{zz}+\cos{\gamma}c_{zz}\right)^2 + \left(\sin{\gamma}c_{xx}+c_{xz}+\cos{\gamma}c_{xz}\right)^2}\notag\\
&& + \sqrt{\left(c_{zz}-\cos{\gamma}c_{zz}\right)^2 + \left(-\sin{\gamma}c_{xx}+c_{xz}-\cos{\gamma}c_{xz}\right)^2}.
\end{eqnarray}

With the inequality Eq. (<ref>), the RHS of Eq. (<ref>) can be upper bounded by

\begin{eqnarray}\label{Supp:UppGeoFunction}
&&\sqrt{\left(1+\cos{\gamma}\right)^2\left(1-c^2_{xz}\right) + \left(\sin{\gamma}c_{xx}+c_{xz}+\cos{\gamma}c_{xz}\right)^2}\notag\\
&& + \sqrt{\left(1-\cos{\gamma}\right)^2\left(1-c^2_{xz}\right) + \left(-\sin{\gamma}c_{xx}+c_{xz}-\cos{\gamma}c_{xz}\right)^2}\notag\\
&=& \sqrt{(1+\cos{\gamma})^2+(\sin{\gamma}c_{xx})^2+2\sin{\gamma}(1+\cos{\gamma})c_{xx}c_{xz}}\notag\\
&& + \sqrt{(1-\cos{\gamma})^2+(\sin{\gamma}c_{xx})^2-2\sin{\gamma}(1-\cos{\gamma})c_{xx}c_{xz}}.
\end{eqnarray}

Without loss of generality, we assume $c_{xx}\geq0$. Then, we can visualize Eq. (<ref>) in Figure <ref>, from which we can see that the maximum of this function reaches when the derivative of $\tau$ is 0, where $\cos{\tau}\equiv c_{xz}$.

The geometric representation of Eq. (<ref>). As shown in Figure <ref>, $\odot O$ is a circle centered at $O$ with a unit radius and $\angle AOC=\gamma$. Let $\frac{ED}{CD}=c_{xx},\cos{\tau}=c_{xz}$, and $DE=DF$. This is well-defined, since $c_{xz}\in[-1, 1]$. Then the formula in Eq. (<ref>) equals $AF+BF$.

By taking derivative of $\tau$, we could have

\begin{eqnarray}
\frac{1+\cos{\gamma}}{\sqrt{(1+\cos{\gamma})^2+(\sin{\gamma}c_{xx})^2+2\sin{\gamma}(1+\cos{\gamma})c_{xx}\cos{\tau}}}\notag\\ =\frac{1-\cos{\gamma}}{\sqrt{(1-\cos{\gamma})^2+(\sin{\gamma}c_{xx})^2-2\sin{\gamma}(1-\cos{\gamma})c_{xx}\cos{\tau}}}.
\end{eqnarray}

With this equation, we can derive another formula,

\begin{eqnarray}
&=&(1+\cos{\gamma})(1-\cos{\gamma}) + (\sin{\gamma}c_{xx})^2,\
\end{eqnarray}

which immediately implies

\begin{eqnarray}
&& + \sqrt{(1-\cos{\gamma})^2+(\sin{\gamma}c_{xx})^2-2\sin{\gamma}(1-\cos{\gamma})c_{xx}c_{xz}}\notag\\
&=& 2\sqrt{
\frac{\prod\limits_{s\in\{-1,1\}}\sqrt{(1+s\cos{\gamma})^2+(\sin{\gamma}c_{xx})^2+2s\sin{\gamma}(1+s\cos{\gamma})c_{xx}\cos{\tau}}}
&=&2\sqrt{\frac{(1+\cos{\gamma})(1-\cos{\gamma}) + (\sin{\gamma}c_{xx})^2}{(1+\cos{\gamma})(1-\cos{\gamma})}}\notag\\
\end{eqnarray}

giving the result

\begin{equation}
S^*= \max_{\rho_{ij},\theta_0,\theta_1,\gamma}S(\rho_{ij},\theta_0,\theta_1,\gamma)= 2\sqrt{1+\alpha^2}.
\end{equation}

For $S\in[2,2\sqrt{2}]$, we derive a valid lower bound to the original primal problem from the inverse of this function,

\begin{equation}
\alpha\geq\alpha(S)\equiv\sqrt{\frac{S^2}{4}-1}.
\end{equation}

For $S<2$, we take the lower bound of $\alpha\geq\alpha(S)\equiv0$. Therefore, we derive the lower bound on the correlation between $\hat{A}_\theta$ and $\hat{B}_\perp$, as given in Lemma <ref>.

§ FINITE-SIZE ANALYSIS

In Sec. <ref>, we have established the relationship between the phase-error probability and the expected values of measurable observables in the experiment. While in practice, the expected values of observables cannot be accessed directly but only frequencies accumulated in a finite number of rounds. The key also has a finite length, hence the key privacy should be expressed in a way of frequency as well. In addition, statistical fluctuations and arbitrary correlations may exist over multiple rounds in the experiment. Here, we shall deal with these problems and derive an estimation of the key privacy in terms of observed statistics, as shown Figure <ref>. This section is organised as follows.

* In Sec. <ref>, we formulate the privacy estimation problem in an explicit optimisation. The key privacy is characterised by the number of probable phase-error patterns, or the cardinality of the smallest phase-error probable set (up to a negligible failure probability). We also introduce the necessary statistical tools for solving the problem, including sample entropy, which will be used to estimate the number of probable phase-error patterns, and martingale-based concentration inequalities, which are used for tackling the non-i.i.d. condition.

* In Sec. <ref>, we introduce the regularised phase-error probability based on the single round analysis.      This subsection provides a technical preparation.

* Based on the ingredients introduced in Sec. <ref> and <ref>, we define the (regularised) phase-error sample entropy in Sec. <ref>. By constructing a corresponding martingale and using Azuma's concentration inequality, we show how the total phase-error sample entropy in an experiment can be related to the expected Bell value. This part is the essence of the finite-size analysis.

* In Sec. <ref>, we apply Azuma's concentration inequality to the estimation of the average expected Bell value in the experiment.

* In Sec. <ref>, we combine the results in Sec. <ref> and <ref> to derive the final privacy estimation result with observed statistics in the experiment. This finishes the finite-size analysis.

* In Sec. <ref>, we present a refined finite-size result using a modified version of Azuma's inequality, namely, Kato's inequality. We explain the necessary replacement and deliver the final result.

every text node part/.style=align=center,
every rectangle node/.style=rounded corners,

[rectangle,draw,text width=6cm] (Obs) at (0,0) Observed statistics in Bell-test rounds, $X_i,Y_i,A_i,B_i$;
[rectangle,draw,text width=6cm] (ExpS) at ($ (Obs.south) + (0,-1cm) $) Average expected Bell value;
[->] (Obs.south) – (ExpS.north) node[midway,left] Concentration inequality node[midway,right] Lemma <ref>, Corollary <ref>;
[rectangle,draw,text width=6cm] (Sam) at ($ (ExpS.south) + (0,-1cm) $) Expected $\xi$-regularised phase-error sample entropy;
[->] (ExpS.south) – (Sam.north) node[midway,left] Bell value $\Rightarrow$ phase error ;
[rectangle,draw,text width=6cm] (USam) at ($ (Sam.south) + (0,-1cm) $) Upper bound on $\xi$-regularised phase-error sample entropy;
[->] (Sam.south) – (USam.north) node[midway,left] Concentration inequality node[midway,right] Lemma <ref>, <ref>, <ref>;
[rectangle,draw,text width=6cm,label=right:Theorem <ref>] (Key) at ($ (USam.south) + (0,-1cm) $) Key privacy (phase-error $\varepsilon$-smallest probable set cardinality);
[->] (USam.south) – (Key.north) node[midway,left] Pattern number counting node[midway,right] Lemma <ref>;

[rectangle,draw,text width=3.5cm] (Regu) at ($ (Sam.east) + (2.5,0) $) $\xi$-regularised phase-error probability;
[rectangle,draw,text width=3.5cm] (Single) at ($ (Regu.east) + (2.5,0) $) Single-round phase-error probability;
[->] (Single.west) – (Regu.east) node[midway,above=.4cm]Definition <ref> (Regu.west) – (Sam.east) node[midway,above=.4cm]Definition <ref>;
[rectangle,draw,text width=3.5cm] (SingleS) at (ExpS-|Single) Single-round expected Bell value $S_{\lambda_i}$;
[->] (SingleS.south) – (Single.north) node[midway,right] Lemma <ref>;
[->] (SingleS.west) – (ExpS.east) node[midway,above] Averaging over $i$ in Eq. (<ref>);

The flowchart of the finite size analysis. To estimate the key privacy using the observed statistics in the Bell-test rounds, we take the following steps. (1) By using Azuma's inequality, the average expected Bell value over rounds can be estimated from the observed Bell test statistics in Lemma <ref> and Corollary <ref>. (2) In each single round, the expected Bell value can be linked with the phase-error probability in Lemma <ref>. (3) Based on the phase error, the statistics of its $\xi$-regularised sample entropy is constructed via Definition <ref> and <ref>. Combined with (1), the expected value of $\xi$-regularised phase-error sample entropy over all key generation rounds can be estimated. (4) By using Azuma's inequality one more time, an upper bound on the value of $\xi$-regularised phase-error sample entropy is derived via Lemma <ref>, <ref>, <ref>. (5) The $\xi$-regularised phase-error sample entropy can be used to upper bound the cardinality of the phase-error $\varepsilon$-smallest probable set via Lemma <ref>. This gives the key privacy estimation result in Theorem <ref>.

§.§ Problem formulation and preliminaries

The target of QKD is essentially a key agreement problem.

The problem can be expressed as an error correction protocol based on the entanglement distillation protocol, where inconsistency of the keys and information leakage are characterised by bit error and phase error to be corrected, respectively [Lo and Chau, 1999, Shor and Preskill, 2000].
The objective is to determine the error pattern via a minimal amount of (bidirectional) communication.
Under this framework, the key privacy is determined by the amount of communication needed for this phase error correction.
The problem of key privacy estimation can be mathematically formulated into bounding the cardinality of the $\varepsilon$-smallest probable (typical) set of phase-error patterns. First, we give the definition of the $\varepsilon$-smallest probable set.

Given $\varepsilon\in[0,\frac{1}{2})$ and a random variable $X\in\mathcal{X}$ defined over a finite alphabet set $|\mathcal{X}|<\infty$ with a probability mass function $p_{X}$, the $\varepsilon$-smallest probable set of $X$ is defined as the smallest set of values $\mathcal{T}_X^\varepsilon$ such that a realisation of $X$ lies in it with a failure probability no larger than $\varepsilon$,

\begin{equation}
\begin{split}
%&\text{s.t. }\mathcal{S} = \left\{{\bf{e}}|\Pr({\bf{E}}\in \mathcal{S})\geq 1-\varepsilon\right\}.\\
&\text{s.t. }\Pr(X\in \mathcal{T})\geq 1-\varepsilon.
\end{split}
\end{equation}

Now we formulate the problem of privacy estimation of the bits from the key generation rounds in DIQKD.

In an $n$-round experiment, suppose a set of events $\{F_i = f_i\}_{i=1}^n$ is observed and $m$ rounds are randomly chosen for key generation $(X_{i_k},Y_{i_k}) = (2,0)$, where $i_k \in \{i_{1},i_{2},\cdots,i_{m}\}$. Given $\varepsilon_{pe}\in[0,\frac{1}{2})$ and the observed data $\{f_i\}$, upper bound the cardinality of the $\varepsilon_{pe}$-smallest probable set of the phase-error patterns $\vec{{E}}_{p}^{\lambda_{i_k}} = \left(E_{p}^{\lambda_{i_1}},\cdots,E_{p}^{\lambda_{i_{m(2,0)}}}\right)$.

After the cardinality of the $\varepsilon_{pe}$-smallest probable set of the phase-error random variables is determined, a privacy amplification procedure can be efficiently carried out by using the family of two-universal hashing functions, corresponding to the phase error correction in an entanglement distillation protocol [Lo and Chau, 1999, Shor and Preskill, 2000]. Given a fixed failure probability of phase error correction $\varepsilon_{pc}\in(0,1)$, the cost for privacy amplification is the logarithm of the $\varepsilon_{pe}$-smallest set cardinality $\left|\mathcal{T}_{\vec{{E}}_{p}^{\lambda_{i_k}}}^{\varepsilon_{pe}}\right|$ plus a constant of $-\log\varepsilon_{pc}$ [Fung et al., 2010].
We emphasize that $\varepsilon_{pe}$ and $\varepsilon_{pc}$ are two different failure probabilities, corresponding to privacy estimation and phase error correction, respectively. In the following we shall focus on the first term and add the second one in the end. Then, the privacy estimation problem becomes the following one,

\begin{equation}\label{Eq:PrivacyEstProb}
\begin{split}
I_{pa} &= \sup_{\Pr{\vec{{E}}_{p}^{\lambda_{i}}}_i, \,\Lambda_i = \lambda_i} \log \left| \mathcal{T}_{\vec{{E}}_{p}^{\lambda_{i_k}}}^{\varepsilon_{pe}}\right| -\log\varepsilon_{pc}, \\
\text{s.t. }F_i &= f_i.
%e_{p}^{\lambda_i}&\leq e_{p}(S^{\lambda_i}),\,\forall i\in[n],
\end{split}
\end{equation}

The optimisation takes over all possible joint probability distributions of $\vec{{E}}_{p}^{\lambda_{i}}$ and system variables values $\Lambda_i=\lambda_i$ in each round that are compatible with the observed statistics, $F_i = f_i$. In the sequential DIQKD protocol, the relationship between the probability a phase error occurs and the expected Bell value in a round conditioned on the past events, as given by Eq. (<ref>), can be utilised for analysis.

In practice, a good upper bound on the solution to the optimisation Eq. (<ref>) suffices for privacy estimation.
A common method in QKD security analysis is to estimate the total number of phase errors, which can be used to derive an upper bound on the privacy amplification cost. In the DIQKD protocol, an upper bound on the total number of phase errors can be derived from the relationship between phase-error probability and expected Bell value in each round given by Eq. (<ref>). However, under a fixed value of the system variable $\Lambda_i=\lambda_i$, the phase-error probability is convex in the expected Bell value. Since the system variables values cannot be accessed and only the average Bell value over rounds can be estimated from observed statistics, in the worst case analysis, one needs to take the function concave closure of Eq. (<ref>) for the estimation of the total number of phase errors. To help understand this point, we provide an example which can actually happen. Suppose in an experiment, all the quantum devices and the quantum systems are first implemented according to the ideal setting, which gives the expected Bell value of $2\sqrt{2}$ in every round. After one half of the rounds in the experiment, suppose the measurement devices break down and give the same output of $1$ irrespective of the measurement bases settings. We would expect that the first half of the rounds behave ideally and the users should obtain perfectly secure key bits in these rounds. In average, the users should obtain about $1/2$ bit of secure key in every key generation round. While if the users evaluate the phase-error rate over the rounds, they shall determine a phase-error rate of approximately $1/4$. When using this parameter for key privacy estimation, the average information leakage would be approximately $h(1/4)$ bit in every key generation round [Fung et al., 2010].
Though the result is tight in the number of phase errors, it does not appear to reach the optimal privacy estimation result. The convexity problem is not removed if one wishes to average the possible values of the system variable in a round and derive a $\Lambda_i$-independent phase-error probability.

Instead of estimating the number of phase errors, we shall take advantage of the concept of sample entropy, a notion originally appeared in classical Shannon theory [Shannon, 1948] (see, Chapter 3 of Ref. [Cover and Thomas, 2012] and Chapter 14.2 of Ref. [Wilde, 2011]).

Given a random variable $X\in\mathcal{X}$ with $|\mathcal{X}|<\infty$ and a probability mass function $p_X$, the sample entropy of a realisation $X=x$ is defined as

\begin{equation}\label{Eq:SampleEntropy}
%e_{p}(S^{\lambda_i}) \\
%\bar{H}(X) = \left\{
%    \begin{tabular}{ll}
%        $-\log[\Pr{X=0}]$, &$X=0$,\\
%        $-\log[\Pr{X=1}]$, &$X=1$.
%        \end{tabular}
%          \right.
\bar{H}(x) =
\end{equation}

The sample entropy can be understood as another random variable derived from $X$ with the same probability mass function $p_X$, which we denote as $\bar{H}(X)$. The name `sample entropy' originates from the fact that the expected value of $\bar{H}(X)$ equals the Shannon entropy of the random variable $X$,

\begin{equation}
\begin{split}
\mathbb{E}_{p_X}[\bar{H}(X)] &= \sum_{x\in\mathcal{X}}p_X(x)\{-\log[p_X(x)]\} \\
\end{split}
\end{equation}

In this work, we mainly deal with binary random variables. Consider $X\in\{0,1\}$ with $\Pr{X=1}=p\in(0,1)$, the Shannon entropy of $X$ equals to

\begin{equation}
\begin{split}
H(X) &= \sum_{x\in\{0,1\}}p_X(x)(-\log[p_X(x)]) \\
&=-(1-p)\log(1-p) - p\log p \\
&= h(p).
\end{split}
\end{equation}

For two parameters $p$ and $\theta$ such that $0\leq p<p+\theta\leq 1/2$, the following inequality holds,

\begin{equation} \label{eq:binaryEntOpt}
\begin{split}
h(p)<-p\log(p+\theta) - (1-p)\log[(1-p)-\theta]<h(p+\theta).
\end{split}
\end{equation}

The proof is rather straightforward and hence is skipped here.

The number of possible realisations of a random variable can be estimated from upper-bounding the sample entropy. Here, we present it as the following lemma.

Given $n$ bits $x_1,\cdots,x_n\in\mathcal{X}=\{0,1\}$, $n$ constants $t_1,\cdots,t_n\in(0,1)$, and $C_U>0$, define the set $\mathcal{T}\subseteq\mathcal{X}^n$

\begin{equation}
\mathcal{T} \equiv \left\{(x_1,\cdots,x_n)\big|-\sum_{i=1}^n\log[q(x_i)] \leq C_U\right\},
\end{equation}

\begin{eqnarray}
q(x_i) \equiv
\left\{
\begin{tabular}{ll} $1-t_i$, & $x_i=0$, \\
$t_i$, & $x_i=1$.
\end{tabular}
\right.
\end{eqnarray}

The cardinality of $\mathcal{T}$ can be upper bounded,

\begin{equation} \label{eq:cardCU}
|\mathcal{T}|\leq 2^{C_U}.
\end{equation}

By the fact that,

\begin{equation}
1 = \sum_{(x_1,\cdots,x_n)\in\{0,1\}^n} 2^{\sum_{i=1}^n \log[q(x_i)]},
\end{equation}

and $\mathcal{T}\subseteq\{0,1\}^n$, we have

\begin{equation}
\begin{split}
1 &= \sum_{(x_1,\cdots,x_n)\in\{0,1\}^n} 2^{\sum_{i=1}^n \log[q(x_i)]} \\
&\geq \sum_{(x_1,\cdots,x_n)\in\mathcal{T}} 2^{\sum_{i=1}^n \log[q(x_i)]} \\
&\geq \sum_{(x_1,\cdots,x_n)\in\mathcal{T}} 2^{-C_U} \\
\end{split}
\end{equation}

Therefore, Eq. (<ref>) holds.

We remark that the function $q(x_i)$ can be understood as the underlying probability corresponding to a random variable. Then, $-\log[q(x_i)]$ becomes the sample entropy of the realization $x_i$. The lemma holds for the general case of non-i.i.d. random variables, which is later used to tackle the non-i.i.d. condition in the finite-size analysis with Azuma's concentration inequality.

Let $(\Omega,\mathcal{A},P)$ be a probability triplet. For every natural number $i\in \mathbb{N}$, let $\mathcal{F}_i$ be a sub-$\sigma$-algebra of $\mathcal{A}$. Then the set

\begin{equation}
\mathbb{F} \equiv \{\mathcal{F}_i\}_{i\in\mathbb{N}}
\end{equation}

is called a filtration if $\mathcal{F}_k\subseteq\mathcal{F}_l,\,\forall k\leq l$.

Let $(\Omega,\mathcal{A},P)$ be a probability triplet and let $\mathbb{F} = \{\mathcal{F}_i\}_{i\in\mathbb{N}}$ be a filtration. For a sequence of random variables $X_0,X_1,X_2,\cdots$ such that $\forall i$, $X_i$ is an $\mathcal{F}_i$-measurable function, the sequence is called a martingale with respect to the filtration $\mathbb{F}$ if $\forall i$,

\begin{equation}
\begin{split}
\mathbb{E}(|X_i|) &<\infty, \\
\mathbb{E}(X_{i+1}|\mathcal{F}_i) &= X_i.
\end{split}
\end{equation}

Given a martingale $\{X_0,X_1,\cdots\}$ with respect to filtration $\mathbb{F}=\{\mathcal{F}_i\}_{i\in\mathbb{N}}$ and finite constants $ c_i\in[0,\infty),i\in\mathbb{N}^+$, if there exist two sets of predictable processes $\{A_i\}_{i\in\mathbb{N}^+}$ and $\{B_i\}_{i\in\mathbb{N}^+}$ where $A_i$ and $B_i$ are $\mathcal{F}_{i-1}$-measurable functions satisfying,

\begin{equation} \label{eq:boundedmartingale}
\begin{split}
A_t\leq X_t-X_{t-1}\leq B_t, \\
B_t - A_t \leq c_t,
\end{split}
\end{equation}

then for all $\delta>0$ and $n\in\mathbb{N}^+$,

\begin{equation}
\Pr(X_n - X_0\geq\delta)\leq \exp\left(-\dfrac{2\delta^2}{\sum_{t=1}^n c_t^2}\right).
\end{equation}

In essence, Azuma's inequality relates the expected values with frequencies. Together with the single-round result in Lemma <ref>, we take the procedure shown in Figure <ref> to derive an upper bound to Problem <ref>.

Because Azuma's inequality is relatively simple in its expression and well-known in the literature, we shall mainly explain how our finite-size analysis works based on this inequality. While for a tighter key rate, one can apply refined versions of Azuma's inequality. In our work, we consider the use of recently developed Kato's inequality [Kato, 2020].

Let $\{X_i\}$ be a list of random variables, and $\{\mathcal{F}_i\}$ be a filtration that identifies random variables, including those variables $\{X_1,\cdots,X_i\}$, i.e., $\mathcal{F}_i$ is a $\sigma$-algebra that satisfies $\mathcal{F}_i\subseteq\mathcal{F}_{i+1}$ and $E(X_{i'}|\mathcal{F}_i)=X_{i'}$ for $i'\leq i$. Suppose that the relation $0\leq X_i\leq1$ holds for any $i$. In this case, for any $n\in\mathbb{N},\delta\in[0,\infty)$ and $\delta'\in\mathbb{R}$, the following inequality holds,

\begin{equation}\label{eq:Kato}
\Pr{\sum_{i=1}^n \frac{\mathbb{E}(X_i|\mathcal{F}_{i-1})}{n} \geq(1+2\delta')\sum_{i=1}^n\frac{X_i}{n}+\delta-\delta'}\leq \exp{-\frac{2n(\delta^2-\delta'^2)}{\left(1+\frac{4\delta'}{3}\right)^2}}.
\end{equation}

When applying Kato's inequality in our analysis, we shall take the following substitution in Eq. (<ref>),

\begin{equation}
\end{equation}

and use the following concentration result,

\begin{equation}\label{eq:reverseKato}
\Pr{\sum_{i=1}^n \frac{\mathbb{E}(X_i|\mathcal{F}_{i-1})}{n} \leq(1+2\delta')\sum_{i=1}^n\frac{X_i}{n}-\delta-\delta'}\leq \exp{-\frac{2n(\delta^2-\delta'^2)}{\left(1+\frac{4\delta'}{3}\right)^2}}.
\end{equation}

If one has empirical knowledge of the behaviour of random variables, then one can optimise the values of $\delta$ and $\delta'$ to obtain better concentration results. To be specific, given failure probability $\varepsilon$ and the number of rounds $n$, if one has an empirical estimation of the random variables $\{X_i\}$, where $\sum_{i=1}^n\frac{X_i}{n}$ shall be close to $\tilde{X}$, then the following optimisation gives the optimal values of $\delta$ and $\delta'$ in Eq. (<ref>),

\begin{equation}\label{Eq:MaxOpt}
\begin{split}		\arg\max_{\delta,\delta'}&\left(1+2\delta'\right)\tilde{X}-\delta-\delta', \\
\text{s.t. }\varepsilon&=\exp{-\frac{2n(\delta^2-\delta'^2)}{\left(1+\frac{4\delta'}{3}\right)^2}}, \\
\delta&>0.
\end{split}
\end{equation}

Similarly, if one has empirical estimation of the conditional expectation variables $\{\mathbb{E}(X_i|\mathcal{F}_{i-1})\}$, where $\sum_{i=1}^n \frac{\mathbb{E}(X_i|\mathcal{F}_{i-1})}{n}$ shall be close to $\tilde{\chi}$, then the following optimisation gives the optimal values of $\delta$ and $\delta'$ in Eq. (<ref>),

\begin{equation}\label{Eq:MinOpt}
\begin{split}		\arg\min_{\delta,\delta'}&\frac{\tilde{\chi}+\delta+\delta'}{1+2\delta'}, \\
\text{s.t. }\varepsilon&=\exp{-\frac{2n(\delta^2-\delta'^2)}{\left(1+\frac{4\delta'}{3}\right)^2}}, \\
\delta&>0.
\end{split}
\end{equation}

The solution to Eq. (<ref>) is given by the following function,

\begin{equation}
\delta'^*=\dfrac{3\left(-16t^2+72t\tilde{X}-72t\tilde{X}^2-9\sqrt{2}\sqrt{2t^2-9t\tilde{X}-8t^2\tilde{X}+45t\tilde{X}^2+8t^2\tilde{X}^2-72t\tilde{X}^3+36t\tilde{X}^4}\right)}{4(-18t+16t^2+81\tilde{X}-72t\tilde{X}-81\tilde{X}^2+72t\tilde{X}^2)},
\end{equation}

and the solution to Eq. (<ref>) is given by the following function,

\begin{equation}
\delta'^*=\dfrac{3\left(-27t-4t^2+72t\tilde{\chi}-72t\tilde{\chi}^2-9\sqrt{t^2-18t\tilde{\chi}-4t^2\tilde{\chi}+90t\tilde{\chi}^2+4t^2\tilde{\chi}^2-144t\tilde{\chi}^3+72t\tilde{\chi}^4}\right)}{4(36t+4t^2+81\tilde{\chi}-72t\tilde{\chi}-81\tilde{\chi}^2+72t\tilde{\chi}^2)},
\end{equation}

where we denote

\begin{equation}
\end{equation}

The optimal values of $\delta$ can be solved by the constraints in Eq. (<ref>) and (<ref>).

§.§ Phase-error probability regularisation

In the finite-size analysis, we shall convert the phase-error probability (as a function of the underlying Bell value given in Eq. (<ref>)) to the sample entropy. A direct conversion would result in the divergence of the logarithm function in Eq. (<ref>) when the phase-error rate approaches zero. Then, the requirement of Eq. (<ref>) cannot be satisfied. In order to solve this divergence problem, we employ a regularised version of the relation between the phase-error probability and the expected Bell value, following Eq. (<ref>).

Given $\xi\in(0,\frac{1}{2})$, the $\xi$-regularised phase-error probability function with respect to the expected Bell value is defined as

\begin{eqnarray}
%e_{p}(S^{\lambda_i}) \\
e_{p}^{\xi}(S) &\equiv& \frac12\cdot\dfrac{e_{p}(S) + \xi}{\frac12+\xi} \nonumber \\ &=& \left\{
\begin{tabular}{ll}
$\dfrac{1 + 2\xi -\sqrt{(S/2)^2-1}}{2(1+2\xi)}$, &$2<S\leq2\sqrt{2},$\\
$\dfrac{1}{2},$ &$0\leq S\leq2$,
\end{tabular}
\right.
\label{Eq:SmoothPhaseErrorProb}
\end{eqnarray}

where $e_{p}(S)$ is the phase-error probability function with respect to $S\in[0,2\sqrt{2}]$ given in Eq. (<ref>). Here, we use the fact that $\max_S{e_{p}(S)}=\frac{1}{2}$.

Here are some properties of $e_{p}^{\xi}(S)$ that will be used for later analysis.

Given $\xi\in(0,\frac{1}{2})$, the function $e_{p}^{\xi}(S)$ defined over the interval $S\in[0,2\sqrt{2}]$ in Eq. (<ref>) has the following properties:

* Monotonicity: $e_{p}^{\xi}(S)$ is monotonically decreasing with respect to $S$.

* Finite range strictly above $0$:

\begin{equation} \label{eq:xiephrange}
\begin{split}
\end{split}
\end{equation}

* Upper bound of $e_{p}(S)$:

\begin{equation} \label{eq:xiephrelax}
\begin{split}
e_{p}^{\xi}(S)\geq e_{p}(S).
\end{split}
\end{equation}

* Concavity: $\forall S_1,S_2$,

\begin{equation} \label{eq:concaveepS}
\begin{split}
h\left[e_{p}^{\xi}\left(\dfrac{1}{2}(S_1+S_2)\right)\right]\geq \dfrac{1}{2}\left(h\left[e_{p}^{\xi}(S_1)\right] + h\left[e_{p}^{\xi}(S_2)\right]\right).
\end{split}
\end{equation}

The proofs are rather straightforward. Eq. (<ref>) can be proved by taking the second derivative of $S$. The last property that $h\left[e_{p}^{\xi}(S)\right]$ is concave in $S$ shall play a vital role in Lemma <ref>. In Figure <ref>, we plot the function over the interval $S\in[2,2\sqrt{2}]$ for $\xi=1\times10^{-7}$.

A diagram of the functions $h[e_{p}^{\xi}(S)],e_{p}^{\xi}(S)$ on the interval $S\in[2,2\sqrt{2}]$. The functions are given in Eq. (<ref>)(<ref>), respectively, and we omit the interval $S\in[0,2]$ in the figure where $h[e_{p}^{\xi}(S)]\equiv1,e_{p}^{\xi}(S)\equiv\frac{1}{2}$.
In the showcase, the parameter $\xi=1\times10^{-7}$. It can be seen that the function $h[e_{p}^{\xi}(S)]$ is concave in $S$, while $e_{p}^{\xi}(S)$ is convex in $S$.

We emphasize that $\xi$ is not a security parameter but a value one can choose freely. In real experiments, $\xi$ could be optimised given the number of rounds and security parameters for a better key rate. Normally, $\xi$ is a small value in comparison to the phase-error probability so that the key rate is not affected much. Furthermore, note that the regularised phase-error probability function needs not necessarily be of the form in Eq. (<ref>). It can be chosen in other forms, as long as it has similar properties as Eq. (<ref>) shown in Lemma <ref>. For instance, $\xi$ does not necessarily be a constant. One can let $\xi$ be a function with respect to $S$. We leave the optimization of the regularisation forms for future research.

§.§ Phase-error sample entropy

Now let us construct the phase-error sample entropy for each round of experiment based on Eq. (<ref>) and show that it satisfies the criteria of Eq. (<ref>) so that we can apply Azuma's inequality.

Consider a DIQKD experiment of $n$ rounds. Before the $i$th round, the experiment runs the same as in the actual protocol. In the $i$th round, the projection $\{\hat{\Pi}_{\lambda_i}^A\otimes\hat{\Pi}_{\lambda_i}^B\}_{\lambda_i}$ is first applied to the system. Construct the filtration $\mathbb{F} = \{\mathcal{F}_j\}_{j=0}^{n}$ with $\mathcal{F}_{j-1}\subseteq\mathcal{F}_{j}$, where $\mathcal{F}_{j-1}$ is the $\sigma$-algebra generated by $\{\Lambda_1,\cdots,\Lambda_j\}$. By our definition of the system variable, the random variable $\Lambda_j$ contains all the information in the system variables with a smaller subscript, hence we can take $\mathcal{F}_{j-1}=\Lambda_j$ for simplicity. For the sake of completeness, define

$\Lambda_{n+1}$ to be an arbitrary quantum operation on the leftover quantum system after the experiment is finished. For the key generation rounds $(X_i,Y_i)=(2,0)$, Alice and Bob need to learn whether a phase error occurs, had they applied the phase-error measurement to the system. For other basis choices, they just apply the original measurements.

On the sub-$\sigma$-algebra $\mathcal{F}_{i-1},i=1,\cdots,n$, define the following random variable

\begin{eqnarray}\label{Eq:RelaxSampleEntropy}
\zeta_{p}^{(i)} =
\left\{
\begin{tabular}{ll} $0$, & if $(X_i,Y_i)\neq(2,0)$, \\
$-\log\left[e_{p}^{\xi}(S^{\lambda_i})\right]$, & if $(X_i,Y_i)=(2,0),\,E_{p}^{\lambda_i}=1$, \\
$-\log\left[1 - e_{p}^{\xi}(S^{\lambda_i})\right]$, & if $(X_i,Y_i)=(2,0),\,E_{p}^{\lambda_i}=0$,
\end{tabular}
\right.
\end{eqnarray}

where $S^{\lambda_i}$ is the expected Bell value in the $i$th round given in Eq. (<ref>). For the key generation rounds $(X_i,Y_i)=(2,0)$, the random variable $\zeta_{p}^{(i)}$ becomes the $\xi$-regularised phase-error sample entropy random variable,

\begin{eqnarray}
{\zeta_{p}^{(i)}}_{|(X_i,Y_i)=(2,0)} = \bar{H}^{\xi}(E_{p}^{\lambda_i}) =
\left\{
\begin{tabular}{ll}
$-\log\left[e_{p}^{\xi}(S^{\lambda_i})\right]$, &$E_{p}^{\lambda_i}=1,$\\
$-\log\left[1-e_{p}^{\xi}(S^{\lambda_i})\right]$, &$E_{p}^{\lambda_i}=0.$
\end{tabular}
\right.
\end{eqnarray}

Now, we can construct a sequence of random variables,

\begin{eqnarray} \label{eq:DeltaRV}
\Delta_{p}^{(l)} = \left\{
\begin{tabular}{ll} $0$, & $l=0$, \\
$\sum_{i=1}^{l}\left(\zeta_{p}^{(i)} - \mathbb{E}_{\Pr{X_i,Y_i,E_{p}^{\lambda_i}}}\left[\zeta_{p}^{(i)}|\mathcal{F}_{i-1}\right]\right)$, & $l=1,\cdots,n$.
\end{tabular}
\right.
\end{eqnarray}

The random variables $\{\Delta_{p}^{(l)}\}_{l\in[n]\cup\{0\}}$ form a bounded martingale with respect to the filtration $\mathbb{F}$. For all $\xi\in(0,\frac{1}{2})$ and $l\geq1$, there are two sets of constants $\{C_L^{(l)}\}_{l\in[n]}$ and $\{C_U^{(l)}\}_{l\in[n]}$, such that

\begin{equation}
\begin{split}
C_L^{(l)}\leq\Delta_{p}^{(l)}-\Delta_{p}^{(l-1)}&\leq C_U^{(l)}, \\
C_U^{(l)}-C_L^{(l)}&\leq c_\xi,
\end{split}
\end{equation}

\begin{equation}\label{Eq:CXi}
c_\xi = -\log\left(\dfrac{\xi}{1+2\xi}\right).
\end{equation}

According to the definition in Eq. (<ref>), the random variable $\Delta_{p}^{(l)}$ has the following recurrence relationship,

\begin{equation}
\begin{split}
\Delta_{p}^{(l)} &= \Delta_{p}^{(l-1)} + \zeta_{p}^{(l)} - \mathbb{E}_{\Pr{X_l,Y_l,E_{p}^{\lambda_l}}}\left[\zeta_{p}^{(l)}|\mathcal{F}_{l-1}\right].
\end{split}
\end{equation}

It follows that

\begin{equation}
\begin{split}
\mathbb{E}_{\Pr{X_l,Y_l,E_{p}^{\lambda_l}}}\left[\Delta_{p}^{(l)}|\mathcal{F}_{l-1}\right] &= \mathbb{E}_{\Pr{X_l,Y_l,E_{p}^{\lambda_l}}}\left[\Delta_{p}^{(l-1)}|\mathcal{F}_{l-1}\right] + \mathbb{E}_{\Pr{X_l,Y_l,E_{p}^{\lambda_l}}}\left[\zeta_{p}^{(l)}|\mathcal{F}_{l-1}\right] - \mathbb{E}_{\Pr{X_l,Y_l,E_{p}^{\lambda_l}}}\left[\zeta_{p}^{(l)}|\mathcal{F}_{l-1}\right] \\
&= \Delta_{p}^{(l-1)},
\end{split}
\end{equation}