# An implementation of range trees with fractional cascading in C++

Vissarion Fisikopoulos

###### Abstract

Range trees are multidimensional binary trees which are used to perform
d-dimensional orthogonal range searching. In this technical report we study
the implementation issues of range trees with fractional cascading, named
layered range trees. We also document our implementation of range trees with
fractional cascading in C++ using STL and generic programming techniques.

##  1 Introduction

This project is an implementation of range trees with fractional cascading,
named layered range trees in C++ using STL and generic programming techniques.
Range trees are multidimensional binary trees which are used to perform
d-dimensional orthogonal range searching. Range trees were discovered
independently by several people including Bentley[1], who also discovered kd-
trees and Lueker, who introduces the technique of fractional cascading for
range trees [7]. An introduction to orthogonal range searching, range trees
and fractional cascading can be found in [6, 9]. In [2] there is a
presentation of a project of efficient implementations of range trees in 2-3
dimensions including layered ones and some experimental results.

##  2 Complexity issues

The range trees answer a d-dimensional range query in time $O(\log^{d}n+k)$,
where $n$ is the whole set of points and $k$ is the set of reported points.
The construction time and the space the tree consume are $O(n\log^{d-1}n)$.
Using fractional cascading we can be benefited by a $\log n$ factor in the
last level of the tree and the resulting time complexity become
$O(\log^{d-1}n+k)$. Intuitively, fractional cascading perform one binary
search instead of two in the last level. The optimal solution to the
orthogonal range search problem is due to Chazelle [5, 4] who propose a
structure with time complexity $O(\log^{c}n+k)$ and $O(n(\log n/\log\log
n)^{d-1})$ space consumption, where $c$ is a constant.

##  3 Range trees in CGAL

Although, CGAL library [3] provides some classes for range trees there is
space for optimizations in that package [10]. Firstly, there is a lack of
recursive construction of d-dimensional range tree and the only way to
construct a range tree of dimension d is to build a tree of dimension 1 and
then make this an associative range tree of a new one which will have
dimension 2. Then one must build a tree of dimension 3 with this tree as an
associative tree and this technique continues until the construction of the
whole d-dimensional tree.

In addition to that, the package uses virtual functions, which increases the
run time and finally there is no fractional cascading.

The proposed approach uses nested templates for the representation of the
$d$-dimensional range tree which is defined in compilation time. The dimension
of the tree must be a constant and defined in the compilation time. In the
last level a fractional cascading structure is constructed.

For example a 4-dimensional range tree of size $n$ with different kind of data
at each layer is given by the following nested templated definition.

⬇

Layered_range_tree <DataClass,

Layered_range_tree <DataClass,

Last_range_tree <DataClass>

>

> tree(n);

Note that for each layer $i<d-1$ the same class Layered_range_tree is used.
The last two layers, in which the fractional cascading is implemented, use the
Last_range_tree class. The DataClass has the definitions of each layer’s own
data along with the comparison operators.

##  4 Software implementation

Essentially, the project was implemented using the C++ language and the STL
library[11]. Concisely, the design uses methods from object oriented as well
as the generic programming style.

### Representation.

The trees are represented as STL vectors. The tree traversals are implemented
using index arithmetic i.e. node’s $i$ parent is $\lfloor i/2\rfloor$, the
left, right child of $i$ is $2i+1$ and $2i+2$ respectively. This method is
optimal for a full, static, binary tree and in our case the third is always
hold. In order to have a full binary tree we replicate the last (biggest in
the fist dimension) point and in the worst case we have a tree the half of
which is useless with no effect to the time complexity (the replicated nodes
would not be visited). In this project we are interested in the static case of
range trees but the design is sufficient for a dynamic implementation in which
the tree nodes must also have some extra pointers. On the other hand,
dynamization of the fractional cascading structure is not trivial [8].

### Construction.

For the construction of the tree we need to sort the input data with respect
to the first coordinate and build recursively (top-down) the main tree in
linear time. For the associative trees we don’t have to sort the input data
again. We build the associative trees in bottom-up manner. Every node merge
the sorted lists of its children in linear time starting from the leaves which
are trivially sorted. Note that this is essentially the same algorithm as
merge-sort.

### Memory consumption.

Even the asymptotic complexity of space stated above ensures that range tree
needs a lot of memory. The only constraint in the number of dimensions of data
is memory. Moreover, from the asymptotic complexity follows that with fixed
memory there is a trade of between the number of data and number of
dimensions. For example see

http://users.uoa.gr/$\sim$vfisikop/compgeom/Layered_Range_trees/examples/Layer
ed_Range_tree_10.cpp

for an example of a range tree over 10-dimensional data.

##  5 Future work

The most important feature for improvement is in the case that the tree is not
full. The solution proposed in the previous section, seams very suboptimal and
is not implemented yet. Another point is that the implementation don’t handle
yet the case that two points have equal coordinates.

##  6 Acknowledgements

This project started as a course project in the graduate course of
Computational Geometry, National and Kapodistrian University of Athens
2008-2009 under the supervision of professor Ioannis Z. Emiris. The C++ code
can be found in:

http://cgi.di.uoa.gr/$\sim$vfisikop/compgeom/Layered_Range_trees

## References

  * [1] J. L. Bentley.  Multidimensional binary search trees used for associative searching.  Commun. ACM, 18(9):509–517, 1975.
  * [2] R. Berinde.  Efficient implementations of range trees.  2007\.
  * [3] C. E. Board.  CGAL User and Reference Manual, 3.4 edition, 2008.
  * [4] B. Chazelle.  Lower bounds for orthogonal range searching: part i. the reporting case.  J. ACM, 37(2):200–212, 1990.
  * [5] B. Chazelle.  Lower bounds for orthogonal range searching: part ii. the arithmetic model.  J. ACM, 37(3):439–463, 1990.
  * [6] M. de Berg, M. van Kreveld, M. Overmars, and O. Schwarzkopf.  Computational Geometry: Algorithms and Applications.  Springer-Verlag, second edition, 2000.
  * [7] G. S. Lueker.  A data structure for orthogonal range queries.  In SFCS ’78: Proceedings of the 19th Annual Symposium on Foundations of Computer Science (sfcs 1978), pages 28–34, Washington, DC, USA, 1978. IEEE Computer Society.
  * [8] K. Mehlhorn and S. Näher.  Dynamic fractional cascading.  Algorithmica, 5:215–241, 1990.
  * [9] D. M. Mount.  Lecture notes: Cmsc 754 computational geometry. lecture 18: Orthogonal range trees.  pages 102–104, 2007.
  * [10] G. Neyer.  Algorithms, complexity, and software engineering in computational geometry.  PhD Thesis, 2000.
  * [11] B. Stroustrup.  The C++ Programming Language (Special 3rd Edition).  Addison-Wesley Professional, February 2000.


# Predicting Critical Biogeochemistry of the Southern Ocean for Climate
Monitoring

Ellen Park
EAPS, MIT
MC&G, WHOI
Jae Deok Kim
EAPS, MIT
Geology & Geophysics, WHOI
Nadege Aoki
EAPS, MIT
Biology, WHOI
Yumeng Melody Cao
EECS
MIT
Yamin Arefeen
EECS
MIT
Matthew Beveridge
EECS
MIT
David Nicholson
Marine Chemistry and Geochemistry
WHOI
Iddo Drori
EECS
MIT

###### Abstract

The Biogeochemical-Argo (BGC-Argo) program is building a network of globally
distributed, sensor-equipped robotic profiling floats, improving our
understanding of the climate system and how it is changing. These floats,
however, are limited in the number of variables measured. In this study, we
train neural networks to predict silicate and phosphate values in the Southern
Ocean from temperature, pressure, salinity, oxygen, nitrate, and location and
apply these models to earth system model (ESM) and BGC-Argo data to expand the
utility of this ocean observation network. We trained our neural networks on
observations from the Global Ocean Ship-Based Hydrographic Investigations
Program (GO-SHIP) and use dropout regularization to provide uncertainty bounds
around our predicted values. Our neural network significantly improves upon
linear regression but shows variable levels of uncertainty across the ranges
of predicted variables. We explore the generalization of our estimators to
test data outside our training distribution from both ESM and BGC-Argo data.
Our use of out-of-distribution test data to examine shifts in biogeochemical
parameters and calculate uncertainty bounds around estimates advance the
state-of-the-art in oceanographic data and climate monitoring. We make our
data and code publicly available.

##  1 Introduction

Ship-based ocean measurements, like those collected by the Global Ocean Ship-
Based Hydrographic Investigations Program (GO-SHIP), provide valuable insight
into ocean carbon uptake, biological processes, circulation, and climate
variability. However, research cruises are expensive, sparse and often
seasonally biased due to weather conditions. The Biogeochemical-Argo (BGC-
Argo) program aims to become the first globally comprehensive sensing array
for ocean ecosystems and biogeochemistry. Yet, profiling floats are limited in
the number of sensors they can support [5]. Developing models which accurately
predict additional features, such as nutrient ratios, from limited sensor data
will broaden the applicability of BGC-Argo floats and allow us to better
monitor and understand changes to the Earth’s climate.

Previous work demonstrates the utility of applying machine learning to cruise
and float data to estimate values of global N2 fixation [13], particulate
organic carbon [11], alkalinity, pH, and nitrate [4]. Bittig et al. [2]
demonstrate advantages of using Bayesian neural networks, which account for
uncertainty around predicted values, to estimate nutrient concentrations, and
D’Alelio et al. [7] show an application of regression methods for examining
interannual variability in primary productivity.

We draw on these methods to develop neural networks trained on cruise data to
predict phosphate and silicate, important nutrients controlling ocean
productivity and biodiversity [14]. This is important because these nutrients
regulate biological processes that remove carbon from the surface ocean at an
annual rate roughly equivalent to annual anthropogenic carbon dioxide
emissions [12],[10]. The Southern Ocean is selected for developing and testing
these models as it is an important global carbon sink and has the most
extensive BGC-Argo float coverage at this time [8].

Figure 1: Transect locations of GO-SHIP oceanographic cruises in the Southern
Ocean, between 03/08/2001-05/02/2019. Latitude 45-90º S, Longitude: -180-180º
E, with surface (P < 10 dbar) values of phosphate (left) and silicate (right)
in $\mu$mol kg-1.

##  2 Methods

### Dataset and training.

We use GO-SHIP data [3] in our training set to train our models. The data set
includes 42,412 data points from Southern Ocean cruises between 2001-2019 as
shown in Figure 1. We use GO-SHIP data for latitude, longitude, pressure,
temperature, salinity, oxygen and nitrate to predict phosphate and silicate.
We restrict our data to latitudes below 45º S, remove rows with missing data
and furthermore follow the standards of the World Ocean Circulation Experiment
Hydrographic Program and use quality control (QC) flags to down-select our
data. We standardize the pressure, temperature, salinity, oxygen, and nitrate
features. The position latitude and longitude data is projected to the WGS 84
/ Antarctic Polar Stereographic coordinate reference system. We do not include
time dependency (month) because initial evaluation of our linear regression
indicates low importance of seasonal variability in predicting silicate and
phosphate variation. We randomly shuffle the feature encoded data into a 9:1
ratio of training to test size and train our model using 10-fold cross-
validation with mean-squared error loss. We select the model with lowest
validation loss to evaluate the testing error for both phosphate and silicate.

### Model.

To evaluate uncertainty when predicting silicate and phosphate from our data,
we train a i) a 1-layer feed-forward, fully connected neural network with
linear activation (equivalent computation to linear regression) and ii)
2-layer feed-forward, fully-connected neural network with 64 hidden units,
ReLU activation, and $p=0.2$ dropout probability. We estimate uncertainty by
sampling using dropout [9], training the network using dropout and then
testing each example by running multiple forward passes with dropout weights.

### Model applications: ESM and BGC-Argo data.

We evaluate our networks performance by comparing our model’s results of
phosphate and silicate to the values predicted from an Earth system model
(ESM). We use the Institut Pierre Simon Laplace Climate Model 5 (IPSL-CM5) [6]
model results from a 10-year historical model run initialized in 2000 and a
30-year projection initialized in 2005. We take the monthly-averaged surface
values (59,088) of temperature, salinity, oxygen, nitrate, phosphate, and
silicate at each location over the historical and predicted span of 35 years
(2000-2035), apply our network model to these surface values (assuming surface
pressure = 5 dbar), and compare our model results to the IPSL-CM5 values of
phosphate and silicate.

Next, we apply our network to test data from BGC-Argo float profiles located
in the Southern Ocean equipped with both dissolved oxygen and nitrate sensors.
There are 175 floats between 2000-2020, measuring a total of 16,710 profiles
that meet these criteria, and we only use data points where all input features
are measured. We apply our network to 181,329 data points and run 100 dropout
iterations to generate standard deviations for our estimates.

##  3 Results

### Comparing linear regression with neural networks

The results from our linear regression analysis reveal a greater uncertainty
in our estimated phosphate values compared to our silicate values.
Additionally, the uncertainty of our silicate results are more uniform over
our test data range, while the phosphate results have a greater uncertainty at
lower values and lower uncertainty at higher ones (see Figure 2 top row). The
uncertainties in our phosphate and silicate estimates are reduced with our
two-layer neural network (see Figure 2 bottom row). The mean squared error
also decreases substantially for both phosphate (MSE Linear: 0.019, MSE NN:
0.0031) and silicate (MSE Linear: 240, MSE NN: 50). The greatest uncertainties
for phosphate are at lower values. For silicate, the greatest uncertainties
are at higher silicate values. This could be a result of the differences in
distribution of these compounds in the water column. Phosphate has greater
variance in the upper water column (where phosphate values are lowest) and
lower variance at depth, while the variance of silicate is more uniform
throughout the water column.

Figure 2: Results of uncertainty calculations using dropout regularization for
linear regression based on OLS and a neural network, with plots for phosphate
shown in (a) and (c) and plots for silicate shown in (b) and (d). Blue lines
show the mean predicted values over 100 iterations and shaded areas represent
95% confidence intervals. The dotted gray line denotes ground truth.

### Neural networks for ESM data.

We compared the ESM output values of phosphate and silicate to our neural-
network predicted values of phosphate and silicate from the ESM features (see
Figure 4 in Appendix). Our neural network under predicts phosphate values
across the Southern Ocean and under predicts silicate values away from the
Antarctic continent compared to the ESM values. However, our neural network is
able to capture the spatial variations for both surface phosphate and
silicate. These results suggest that our neural network model is able to
capture processes modeled by the ESM. However, there are still discrepancies
between these two model types. Based on these results, we believe our neural
network has a high enough performance to apply to BGC-Argo data to estimate
phosphate and silicate values from true observations.

### Neural networks for BGC-Argo data.

Our neural network applied to BGC-Argo data predicts similar spatial patterns
of phosphate and silicate to those measured by GO-SHIP and modeled by the ESM
(see Figure 3). However, there are a few float trajectories that have
noticeably different values from other floats in the region. While this could
be due to local biogeochemical processes, it likely is due to sensor noise or
drift that was missed during quality control. The uncertainties estimated for
phosphate are generally low and uniform throughout the region, while the
uncertainty estimates for silicate present similar spatial patterns as the
mean value estimates, with high uncertainties near the continent. This
suggests that there is a systematic error close to the continent, which could
be attributed to ice dynamics causing higher variability in our features.
These results suggest a relationship between latitude and silicate
distributions.

### Limitations.

Our neural network models are generally successful, demonstrating high
potential for progress in this application. However, our proof-of-concept
implementation leaves areas for improvement. We plan to improve our models by:
(i) including a temporal component and using a spatial-temporal graph neural
network representation; (ii) preserving the spatial relationships within the
training data using a graph neural network; and (iii) training the models on a
subset of shallower GO-SHIP data to better compare our model output to the
surface model results from the ESM.

Figure 3: Results from applying our neural network to predict phosphate and
silicate ($\mu$mol kg-1) using BGC-Argo float data. Top row: Predicted mean
values for phosphate (left) and silicate (right). Middle row: Predicted
standard deviations for phosphate (left) and silicate (right). There is
systematically higher uncertainty near the continent for silicate values.

##  4 Conclusions

Our neural networks, trained on ship-based measurements using dropout
regularization to predict dissolved phosphate and silicate values in the
Southern Ocean, performed better than our linear regression models. However,
the neural networks showed variable levels of uncertainty across the ranges of
both predicted variables. When we apply our neural network models to the ESM
data, we are able to evaluate our empirical models’ performance relative to
the bio-physical models in the surface ocean. We then further apply the neural
networks to the BGC-Argo data to demonstrate the models’ goal application and
to generally compare the results to the GO-SHIP and ESM data. Ultimately, our
models are successful and provide a workflow that may be used and scaled
globally and applied to the expanding BGC-Argo fleet. Furthermore, our results
demonstrate the utility of applying machine-learning based regression methods
to estimate additional biogeochemical parameters from a limited set of
oceanographic variables. This provides additional means for the scientific
community to leverage existing earth system observational programs to monitor
the climate system and its changes. All code is written in Python and shared
online in an anonymous
Dropbox111https://www.dropbox.com/sh/tpr3rw2i5g1fmdw/AABBZHyZ8erp_1hy6iEutix8a?dl=0.
The ESM [15] and BGC-Argo data [1] are publicly available.

## Acknowledgements

We acknowledge model output from IPSL via CMIP and float data from the
International Argo Program and the national programs that contribute to it.
The Argo Program is part of the Global Ocean Observing System. Argo (2021). DN
was supported by NSF$\\#$1946578\. EP was supported by NSF$\\#$1756613\. ID
thanks Google for a cloud educational grant.

## References

  * [1] Argo.  Argo float data and metadata from Global Data Assembly Centre (Argo GDAC).  https://doi.org/10.17882/42182, 9 2021.
  * [2] Henry C Bittig, Tobias Steinhoff, Hervé Claustre, Björn Fiedler, Nancy L Williams, Raphaëlle Sauzède, Arne Körtzinger, and Jean-Pierre Gattuso.  An alternative to static climatologies: robust estimation of open ocean CO2 variables and nutrient concentrations from T, S, and O2 data using Bayesian neural networks.  Frontiers in Marine Science, 5:328, 2018.
  * [3] Carbon Hydrographic Data Office.  GO-SHIP data.  https://cchdo.ucsd.edu, 9 2021.
  * [4] BR Carter, RA Feely, NL Williams, AG Dickson, MB Fong, and Y Takeshita.  Updated methods for global locally interpolated estimation of alkalinity, pH, and nitrate.  Limnology and Oceanography: Methods, 16(2):119–131, 2018.
  * [5] Fei Chai, Kenneth S Johnson, Hervé Claustre, Xiaogang Xing, Yuntao Wang, Emmanuel Boss, Stephen Riser, Katja Fennel, Oscar Schofield, and Adrienne Sutton.  Monitoring ocean biogeochemistry with autonomous platforms.  Nature Reviews Earth & Environment, 1(6):315–326, 2020.
  * [6] Climate Modeling Center.  Institut Pierre Simon Laplace Climate Model 5 (IPSL-CM5).  https://cmc.ipsl.fr/international-projects/cmip5/, 9 2021.
  * [7] Domenico D’Alelio, Salvatore Rampone, Luigi Maria Cusano, Valerio Morfino, Luca Russo, Nadia Sanseverino, James E Cloern, and Michael W Lomas.  Machine learning identifies a strong association between warming and reduced primary productivity in an oligotrophic ocean gyre.  Scientific Reports, 10(1):1–12, 2020.
  * [8] Nicolas Gruber, Peter Landschützer, and Nicole S Lovenduski.  The variable Southern Ocean carbon sink.  Annual Review of Marine Science, 11:159–186, 2019.
  * [9] Alex Kendall and Yarin Gal.  What uncertainties do we need in Bayesian deep learning for computer vision?  In Advances in Neural Information Processing Systems, volume 30, 2017.
  * [10] NOAA Global Monitoring Laboratory.  Carbontracker ct2019b: Flux time series.
  * [11] R Sauzède, J Emmanuel Johnson, H Claustre, G Camps-Valls, and AB Ruescas.  Estimation of oceanic particulate organic carbon with machine learning.  ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2:949–956, 2020.
  * [12] D.A. Siegel, K.O. Buesseler, S.C. Doney, M.J. Sailley, M.J. Behrenfeld, and P.W. Boyd.  Global assessment of ocean carbon export by combining satellite observations and food-web models.  Global Biogeochemical Cycles, 28:181–196, 2014.
  * [13] Weiyi Tang, Zuchuan Li, and Nicolas Cassar.  Machine learning estimates of global marine nitrogen fixation.  Journal of Geophysical Research: Biogeosciences, 124(3):717–730, 2019.
  * [14] Thomas S Weber and Curtis Deutsch.  Ocean nutrient ratios governed by plankton biogeography.  Nature, 467(7315):550–554, 2010.
  * [15] World Climate Research Programme (WCRP).  Coupled Model Intercomparison Project.  https://esgf-node.llnl.gov/projects/cmip6, 9 2021.

## Appendix

Figure 4 demonstrates our neural network model output values of phosphate and
silicate to our neural-network predicted values of phosphate and silicate from
the ESM features. Our neural network under predicts phosphate values across
the Southern Ocean and under predicts silicate values away from the Antarctic
continent compared to the ESM predicted values. However, our neural network is
generally able to capture the spatial variations in both phosphate and
silicate values. These results suggest that our neural network model is able
to capture processes modeled by the ESM.

Figure 4: IPSL-CM5 model values for parameters of interest and results from
applying our neural network to predict phosphate and silicate in this model
space. Top row: Unchanged values from IPSL-CM5 model. Middle row: Predicted
values from our neural network using ESM predictions for all features. Bottom
row: ESM - NN. These figures show general agreement between these two
approaches, with a systematic underestimation of phosphate by our neural
network compared to the ESM and greater disagreement on both variables near
the continent.


# Real-time operation of a multi-rate, multi-protocol quantum key distribution
transmitter

Innocenzo De Marco,1,2,* Robert I. Woodward,1 George L. Roberts,1,3 Taofiq K.
Paraïso,1 Thomas Roger,1 Mirko Sanzaro,1 Marco Lucamarini,1 Zhiliang Yuan,1
and Andrew J. Shields1 1Toshiba Europe Ltd, 208 Cambridge Science Park,
Cambridge, CB4 0GZ, United Kingdom
2School of Electronic and Electrical Engineering, University of Leeds, Leeds,
LS2 9JT, United Kingdom
3Cambridge University Engineering Department, 9 JJ Thomson Avenue, Cambridge,
CB3 0FA, United Kingdom<EMAIL_ADDRESS>
###### Abstract

Quantum key distribution (QKD) is the best candidate for securing
communications against attackers, who may in the future exploit quantum-
enhanced computational powers to break classical encryption. As such, new
challenges are arising from our need for large-scale deployment of QKD
systems. In a realistic scenario, transmitting and receiving devices from
different vendors should be able to communicate with each other without the
need for matching hardware. Therefore, practical deployment of QKD would
require hardware capable of adapting to different protocols and clock rates.
Here, we address this challenge by presenting a multi-rate, multi-protocol QKD
transmitter linked to a correspondingly adaptable QKD receiver. The
flexibility of the transmitter, achieved by optical injection locking, allows
us to connect it with two receivers with inherently different clock rates.
Furthermore, we demonstrate the multi-protocol operation of our transmitter,
communicating with receiving parties employing different decoding circuits.

##  I Introduction

Quantum key distribution (QKD) allows users to communicate with information
theoretical security [1]. It has become a strong candidate to resolve the
imminent threat posed by quantum computers[2] to many existing cryptographic
protocols based on complexity theory [3]. QKD, on the other hand, bases its
security on the laws of quantum mechanics and would not be affected by the
advent of quantum computers. There have been many impressive demonstrations of
point-to-point QKD over fibre links, including key sharing at 10 Mbit/s [4]
and at a distance of 421 km [5] for a point-to-point link of optical fibre.
Such distances can be further improved thanks to the novel twin-field QKD
protocol [6], which has the capability to reach more than 500 km [7, 8].

Large-scale implementations of QKD will likely see users having different
devices from different manufacturers. This calls for an urgent need for
interoperability. In a realistic scenario, users would likely choose their
device based on required performance and system cost, where different vendors
might offer devices operating at different clock rates or via different
protocols. [9] Much of the current research within QKD aims at improving
specific systems, while little consideration is given to interoperability
between different systems. This has led to the situation where dedicated
hardware is required to implement separate protocols and to operate at a fixed
clock rate. Multi-rate, multi-protocol capability of the transmitters and
receivers are hence highly desirable in this scenario [10, 11]. However, much
of the research in this direction has focussed solely on highlighting the
flexibility of the transmitter by implementing the protocols separately. In a
scenario where communication with several parties is required, being able to
switch between clock rates and protocols in real time is crucial for efficient
communication.

In this manuscript we demonstrate real-time, multi-clock and multi-protocol
continuous operation of a directly phase-modulated QKD transmitter [12, 13].
By changing only the driving signal sent to our transmitter,we are able to
change its operating regime in real time to communicate with a different
receiving device. The system stabilisation happens within a few seconds,
without loss of integrity or degradation of the Quantum Bit Error Rate (QBER)
and Secure Key Rates (SKR) afterwards.

##  II Experimental Realisation

### Protocols

We implement three QKD protocols. The first is the differential phase shift
(DPS) protocol [14]. This protocol is based on the encoding of information in
the phase difference of consecutive pulses. Alice can encode her information
with $\\{0,~{}\pi\\}$ phase shifts, and Bob will decode it using an asymmetric
Mach-Zehnder interferometer (aMZI).

The second protocol is the time-bin encoded BB84 protocol [15] with decoy
states [16, 17, 18]. Here, the information is carried by the phase difference
in pulse pairs. Pulses belonging to different pairs need to have a random
phase difference. Such randomness is necessary to minimise the amount of
information an eavesdropper can retrieve from the pulse [19]. Alice encodes
her qubits in two different bases: for the $\mathbf{X}$ basis, phase shifts of
$\\{0,~{}\pi\\}$ are used. For the $\mathbf{Y}$ basis, phase shifts of
$\\{\pi/2,~{}3\pi/2\\}$ are used. The intensity of the optical pulses is
modulated to implement the decoy states technique.

Finally, the last protocol we implement is the Coherent One Way (COW) protocol
[20]. The information is encoded in the time bins of pulse pairs, the
coherence between which is used to check whether these pulses have been
tampered with.

As a proof-of-principle demonstration, we consider the protocols’ asymptotic
secure key rates. A full finite-size analysis is outside the scope of the
present paper and would not change the significance of our results. Moreover,
to simplify the data collection, data is collected in one basis only for the
BB84 protocol, with the assumption that the two bases are chosen with
identical probabilities and have similar phase errors. Finally, since the data
is recorded and measured as a cumulative histogram of a repeating pattern, one
detector is sufficient to measure the QBER. This all means that we only need
one detector for the BB84 and DPS protocols and two detectors for the COW
protocol (one for the time-bin encoding, one for decoy detection). This also
means that the same receiver can be used for all three protocols at a given
clock rate. The input of the chip is split between the straight waveguide and
the interferometer, with a $\sim~{}50:50$ splitting ratio, which allows us to
measure all the quantities we need at once. While not the case in a realistic
scenario, this is reasonable for a proof of principle experiment as we are
able to extract all the needed information from this simplified setup.

It is important to note that security proofs for the three protocols show that
they have significant differences in their security. For example, the decoy-
state BB84 protocol is secure against coherent attacks, whereas the security
proofs for the DPS and COW protocols are based on collective attacks. For this
reason, the comparison between the SKRs obtained with the BB84 [21], DPS [22]
and COW [23] protocols should be taking this into account.

### Modulator-free transmitter

The encoding is based on the combination of two well-known techniques in laser
physics: optical injection locking (OIL) [24, 25] and direct phase modulation
[26]. This approach has been proven to effectively remove the need for a phase
modulator in QKD [12]: this makes our transmitter versatile while also
reducing the number of optical elements in the setup. Another advantage of our
transmitting setup is the lack of an aMZI. This is useful for two main
reasons: first of all, this greatly reduces losses since there is no mismatch
between two arms of different length. In a fibre-based system this does not
have a big impact, but chip-based experiments suffer from higher losses, hence
a 500 ps or 1 ns delay line would lead to a power mismatch between the two
arms. For this reason, chip-based experiments usually avoid embedding an aMZI
in the transmitter, resorting to modulating every pulse with a phase modulator
[11] or exploiting the directly phase-modulated setup [13]. The second
advantage of an aMZI-free setup is the ability to use the same setup to encode
different protocols. This is crucial to our experiment, as it allows us to
change different protocols and/or clock rates at will by simply changing the
modulation of the driving current, with a transient of less than 5 seconds
between every change.

The experimental setup is shown in Fig. 1. We use arbitrary waveform
generators (AWG) with a sampling rate of 24 Gs/s and vertical resolution of 8
bit to drive the lasers at GHz clock rates and synchronise the system. A phase
encoding laser injects light into a second, injection locked laser through a
circulator. These are both discrete optics, off-the-shelf DFB lasers, with a
bandwidth of ¿10 GHz. An intensity modulator sets the signal and decoy levels
for the system. The quantum channel is simulated by a variable optical
attenuator (VOA), fibre-coupled to the transmitter and the receiver. A MEMS
switch is used to select the correct receiver chip, according to the driving
signal sent to the transmitter setup. At the output of the receiver chips,
optical fibres are coupled to superconducting nanowire single photon detectors
(SNSPDs) [27]; each of the outputs (the time-bin encoding waveguide for COW
and one of the interferometer outputs for all three protocols, as mentioned in
the previous paragraph) is connected to a detector. The SNSPDs’ output is read
by a single-photon counting module (SPCM) which digitises the data and sends
the results to Bob’s computer where the QBER and key rates are computed.

Figure 1: Experimental setup Schematic of the experimental setup used to carry
out the experiment. DC and RF signals are combined through a bias-tee and sent
to the phase encoding and injection locked lasers. A circulator prevents light
from the latter going back to the phase encoding laser. The RF signals are
changed to encode different protocols and clock rates. An optical MEMS switch
selects the correct receiver chip, which is out-coupled to SNSPDs. Figure 2:
Modulation signals Driving signals from phase encoding and injection locked
lasers for the COW, DPS and BB84 protocols. For each protocol, the top plot
represents the electrical driving signals, the bottom plot represents the
optical output. The symbol between consecutive pulses represents the relative
phase difference, where “R” refers to a random phase difference between
pulses.

We encode our information as shown in Fig 2. For the COW and DPS protocol, the
phase encoding laser is always biased over its threshold to produce
continuous-wave (CW) emission; additionally, in the DPS case, a small current
modulation, synchronised to the interval of two injection locked pulses, is
applied when a $\pi$ phase modulation is required. The BB84 protocol requires,
in addition to the phase modulation, a random global phase: only pulses
belonging to the same pair of time-bins have a set phase difference. To this
end, the phase encoding laser is driven periodically above and below the
lasing threshold, exploiting the inherent randomness of gain-switching [28,
29].

### Integrated receivers

The receivers are $\mathrm{SiO_{x}N_{y}}$ photonic chips, whose interferometer
length determine the clock rates they work at. We use receiver chips whose
interferometer delay lengths are 500 ps and 400 ps, achieving clock rates of 2
and 2.5 GHz respectively.

Our QKD receivers are manufactured on a silicon-based substrate, which allows
for low losses and easy integration. Our receiver chips are designed to have
different interferometers, each one decoding information for a different
protocol.

The interferometers are tuned by means of thermo-optic phase shifters. Such
elements can be driven with a DC current source; a $\pi$ phase shift is
obtained with a voltage of around $15~{}\mathrm{V}$. The phase shift induced
by the heaters can be used to direct light towards one arm or the other of the
interferometer, or to balance the power between the two arms. This is
particularly important since the long arm will cause a power imbalance at the
output coupler: the length of the delay line will cause more losses. For this
experiment, the total loss for the interferometer circuit on the
$2.5~{}\mathrm{GHz}$ chip is measured to be $10.1~{}\mathrm{dB}$, while the
loss for the $2~{}\mathrm{GHz}$ chip is $6.7~{}\mathrm{dB}$. The straight
waveguides used for the COW protocol have losses that are
$\sim~{}3~{}\mathrm{dB}$ less than the interferometer ones.

The main contribution to the losses is the propagation loss ($\sim
0.2~{}\mathrm{dB/cm}$) in the delay line, however a big contribution is also
coming from fabrication imperfections and fibre coupling. All these cause the
excess loss in the $2.5~{}\mathrm{GHz}$ chip compared to the
$2~{}\mathrm{GHz}$ chip, as the statistical imperfections of that chip cause
losses that overweigh the lower loss coming from the shorter delay line.

The output waveguides are out-coupled through optical fibres to SNSPDs, with
an efficiency of $44\%$ and dark count rates of $\sim 10~{}\mathrm{Hz}$.

##  III Results

Fig. 3 shows the performance of the transmitter at two different clock rates
using the BB84 protocol. The loss considered in the plots includes only the
quantum channel attenuation and the loss from the optical switch. As shown in
the figure, the 2.5 GHz performs worse than the 2 GHz receiver at the same
channel loss. This is due to the excess losses in the chip mentioned in the
previous paragraph. The top axis of Fig. 3 shows instead the total loss,
including the receiver chip loss. This allows a clearer comparison between the
chips, and shows how the higher clock rate would indeed yield a higher key
rate as expected, if the chips had equal loss.

Figure 3: Secure key rates BB84 secure key rates and QBER vs channel loss for
2 GHz and 2.5 GHz. The color red indicates the QBER, teal the raw count rates
and orange the SKR. The points correspond to measured data, the line to the
simulated behaviour.

We then proceed to the main goal of the paper, demonstrating the flexibility
of our system. Our transmitter is set to implement different protocols at
different clock rates. A signal is then sent to the system, triggering the
clock rate and protocol change after 10 minutes. When this happens, a first
point is recorded with a high QBER and, consequently, no positive key rate.
The main reason behind this is that the AWG’s electronics takes some time to
settle to a stable output. This time is below 5 seconds. Results are shown in
Fig. 4. The stability of the system allows for a reasonably constant secure
key rate (SKR) during a 10-minute time window, at a channel loss of
$14~{}\mathrm{dB}$.

The QBER is stable around values of $2.7$% for BB84 at both clock rates and
DPS, while it is around $0.7$% for the COW protocol, due to the absence of
phase errors in this protocol. This yields key rates of $0.5$, $0.4$ and
$2.5~{}\mathrm{Mbps}$ for BB84, DPS and COW, respectively.

Figure 4: Performance of the universal transmitter Results obtained encoding
the BB84 protocol at different clock rates (left) and encoding different
protocols at a 2 GHz rate (right). The first point after every change of clock
rate or protocol, with a high QBER, does not result in a positive SKR. The
data is collected at a channel loss of 14 dB. The 2.5 GHz regime has lower
count rates than the 2 GHz regime due to the higher losses in the receiver
chip.

##  IV Conclusion

Our experiments show the feasibility of having a single transmitter
communicating with receivers employing different clock rates and protocols.
This is possible because of the directly phase-modulated setup which allows
flexibility to change the operating conditions by simply modifying the
electrical driving signals. The protocols and clock rates are set up to
continuously change, leading to the system reconfiguring in real time while
still maintaining a low QBER and high SKR. We showed an effective setup time
lower than $5~{}\mathrm{s}$. This was limited by the driving electronics,
mainly the AWG, needing time to settle to the desired operation regime.
Reduced times can be certainly obtained by using faster driving electronics,
for instance, a custom-designed FPGA board.

On the receiver side, two different chips were used for the two different
clock rates. Tuneable delay length can be considered in order to demonstrate
multi-rate capabilities of the receiver, however it must be noted that adding
reconfigurable components would add to the complexity of the chip and could
cause issues such as thermal fluctuations. An alternative approach, since the
advantage of integrated photonics lies in the compactness of devices, might be
to implement different interferometers on the same chip.

Our result is a step forward towards interoperability between devices from
different vendors and paves the way for large-scale, collaborative deployment
of QKD systems. In this respect, we believe that our work will have a positive
impact on the on-going efforts in QKD standardization.

## Acknowledgments

I.D.M. acknowledges funding from the European Union’s Horizon 2020 research
and innovation programme under the Marie Skłodowska-Curie grant agreement No
675662.

G.L.R. gratefully acknowledges financial support from the EPSRC CDT in
Integrated Photonic and Electronics Systems, Toshiba Europe Limited and an
industrial fellowship with The Royal Commission for the Exhibition of 1851.

This work has been partially funded by the Innovate UK project AQUASEC, as
part of the UK National Quantum Technologies Programme.

## Disclosures

The authors declare no conflicts of interest.

## Data availability

Data underlying the results presented in this paper are not publicly available
but may be obtained from the authors upon reasonable request.

## References

  * Scarani  _et al._ [2009] V. Scarani, H. Bechmann-Pasquinucci, N. J. Cerf, M. Dušek, N. Lütkenhaus, and M. Peev, The security of practical quantum key distribution, Rev. Mod. Phys. 81, 1301 (2009).
  * Arute  _et al._ [2019] F. Arute, K. Arya, R. Babbush, D. Bacon, J. C. Bardin, R. Barends, R. Biswas, S. Boixo, F. G. S. L. Brandao, D. A. Buell, B. Burkett, Y. Chen, Z. Chen, B. Chiaro, R. Collins, W. Courtney, A. Dunsworth, E. Farhi, B. Foxen, A. Fowler, C. Gidney, M. Giustina, R. Graff, K. Guerin, S. Habegger, M. P. Harrigan, M. J. Hartmann, A. Ho, M. Hoffmann, T. Huang, T. S. Humble, S. V. Isakov, E. Jeffrey, Z. Jiang, D. Kafri, K. Kechedzhi, J. Kelly, P. V. Klimov, S. Knysh, A. Korotkov, F. Kostritsa, D. Landhuis, M. Lindmark, E. Lucero, D. Lyakh, S. Mandrà, J. R. McClean, M. McEwen, A. Megrant, X. Mi, K. Michielsen, M. Mohseni, J. Mutus, O. Naaman, M. Neeley, C. Neill, M. Y. Niu, E. Ostby, A. Petukhov, J. C. Platt, C. Quintana, E. G. Rieffel, P. Roushan, N. C. Rubin, D. Sank, K. J. Satzinger, V. Smelyanskiy, K. J. Sung, M. D. Trevithick, A. Vainsencher, B. Villalonga, T. White, Z. J. Yao, P. Yeh, A. Zalcman, H. Neven, and J. M. Martinis, Quantum supremacy using a programmable superconducting processor, Nature 574, 505 (2019).
  * Shor [1999] P. W. Shor, Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM review 41, 303 (1999).
  * Yuan  _et al._ [2018] Z. Yuan, A. Plews, R. Takahashi, K. Doi, W. Tam, A. Sharpe, A. Dixon, E. Lavelle, J. Dynes, A. Murakami, M. Kujiraoka, M. Lucamarini, Y. Tanizawa, H. Sato, and A. J. Shields, 10-mb/s quantum key distribution, Journal of Lightwave Technology 36, 3427 (2018).
  * Boaron  _et al._ [2018] A. Boaron, B. Korzh, R. Houlmann, G. Boso, D. Rusca, S. Gray, M.-J. Li, D. Nolan, A. Martin, and H. Zbinden, Simple 2.5 ghz time-bin quantum key distribution, Applied Physics Letters 112, 171108 (2018).
  * Lucamarini  _et al._ [2018] M. Lucamarini, Z. L. Yuan, J. F. Dynes, and A. J. Shields, Overcoming the rate–distance limit of quantum key distribution without quantum repeaters, Nature 557, 400 (2018).
  * Minder  _et al._ [2019] M. Minder, M. Pittaluga, G. L. Roberts, M. Lucamarini, J. F. Dynes, Z. L. Yuan, and A. J. Shields, Experimental quantum key distribution beyond the repeaterless secret key capacity, Nature Photonics 13, 334 (2019).
  * Fang  _et al._ [2020] X.-T. Fang, P. Zeng, H. Liu, M. Zou, W. Wu, Y.-L. Tang, Y.-J. Sheng, Y. Xiang, W. Zhang, H. Li, Z. Wang, L. You, M.-J. Li, H. Chen, Y.-A. Chen, Q. Zhang, C.-Z. Peng, X. Ma, T.-Y. Chen, and J.-W. Pan, Implementation of quantum key distribution surpassing the linear rate-transmittance bound, Nature Photonics 14, 422 (2020).
  * Moseley  _et al._ [2004] S. Moseley, S. Randall, and A. Wiles, In pursuit of interoperability, International Journal of IT Standards and Standardization Research 2, 34 (2004).
  * Korzh  _et al._ [2013] B. Korzh, N. Walenta, R. Houlmann, and H. Zbinden, A high-speed multi-protocol quantum key distribution transmitter based on a dual-drive modulator, Optics Express 21, 19579 (2013).
  * Sibson  _et al._ [2017] P. Sibson, J. E. Kennard, S. Stanisic, C. Erven, J. L. O’Brien, and M. G. Thompson, Integrated silicon photonics for high-speed quantum key distribution, Optica 4, 172 (2017).
  * Yuan  _et al._ [2016] Z. L. Yuan, B. Fröhlich, M. Lucamarini, G. L. Roberts, J. F. Dynes, and A. J. Shields, Directly phase-modulated light source, Physical Review X 6, 031044 (2016).
  * Paraïso  _et al._ [2019] T. K. Paraïso, I. De Marco, T. Roger, D. G. Marangon, J. F. Dynes, M. Lucamarini, Z. Yuan, and A. J. Shields, A modulator-free quantum key distribution transmitter chip, npj Quantum Information 5, 42 (2019).
  * Inoue  _et al._ [2003] K. Inoue, E. Waks, and Y. Yamamoto, Differential-phase-shift quantum key distribution using coherent light, Physical Review A 68, 022317 (2003).
  * Bennett and Brassard [1984] C. H. Bennett and G. Brassard, Quantum cryptography: Public key distribution and coin tossing, in  _International Conference on Computer System and Signal Processing, IEEE, 1984_ (1984) pp. 175–179.
  * Lo  _et al._ [2005] H.-K. Lo, X. Ma, and K. Chen, Decoy state quantum key distribution, Physical Review Letters 94, 230504 (2005).
  * Hwang [2003] W.-Y. Hwang, Quantum key distribution with high loss: Toward global secure communication, Physical Review Letters 91, 057901 (2003).
  * Wang [2005] X.-B. Wang, Beating the photon-number-splitting attack in practical quantum cryptography, Physical Review Letters 94, 230503 (2005).
  * Lo and Preskill [2007] H.-K. Lo and J. Preskill, Security of quantum key distribution using weak coherent states with nonrandom phases, Quantum Information & Computation 8, 431 (2007).
  * Stucki  _et al._ [2005] D. Stucki, N. Brunner, N. Gisin, V. Scarani, and H. Zbinden, Fast and simple one-way quantum key distribution, Applied Physics Letters 87, 194108 (2005).
  * Ma  _et al._ [2005] X. Ma, B. Qi, Y. Zhao, and H.-K. Lo, Practical decoy state for quantum key distribution, Physical Review A 72, 012326 (2005).
  * Waks  _et al._ [2006] E. Waks, H. Takesue, and Y. Yamamoto, Security of differential-phase-shift quantum key distribution against individual attacks, Physical Review A 73, 012344 (2006).
  * Stucki  _et al._ [2009] D. Stucki, C. Barreiro, S. Fasel, J.-D. Gautier, O. Gay, N. Gisin, R. Thew, Y. Thoma, P. Trinkler, F. Vannel, _et al._ , Continuous high speed coherent one-way quantum key distribution, Optics Express 17, 13326 (2009).
  * Le Binh [2018] N. Le Binh,  _Optical modulation: Advanced techniques and applications in transmission systems and networks_ , Optical science and engineering (Taylor & Francis a CRC title part of the Taylor & Francis imprint a member of the Taylor & Francis Group the academic division of T&F Informa plc, Boca Raton, 2018).
  * Barnes and Barnes [1993] N. P. Barnes and J. C. Barnes, Injection seeding i: Theory, IEEE Journal of Quantum Electronics 29, 2670 (1993).
  * Shirasaki  _et al._ [1988] M. Shirasaki, H. Nishimoto, T. Okiyama, and T. Touge, Fibre transmission properties of optical pulses produced through direct phase modulation of dfb laser diode, Electronics Letters 24, 486 (1988).
  * Chandra M. Natarajan  _et al._ [2012] Chandra M. Natarajan, Michael G. Tanner, and Robert H. Hadfield, Superconducting nanowire single-photon detectors: Physics and applications, Superconductor Science and Technology 25, 063001 (2012).
  * Jofre  _et al._ [2011] M. Jofre, M. Curty, F. Steinlechner, G. Anzolin, J. P. Torres, M. W. Mitchell, and V. Pruneri, True random numbers from amplified quantum vacuum, Optics Express 19, 20665 (2011).
  * Yuan  _et al._ [2014] Z. L. Yuan, M. Lucamarini, J. F. Dynes, B. Fröhlich, A. Plews, and A. J. Shields, Robust random number generation using steady-state emission of gain-switched laser diodes, Applied Physics Letters 104, 261112 (2014).