# Quantum Verification of Minimum Spanning Tree

Mark Heiligman  Intelligence Advanced Research Projects Activity, Office of
the Director of National Intelligence, Washington, D.C.
mark.i.heiligmanugov.gov

(January 29, 2011 ; 1926 ; 2006 ; 1997 ; 1997 ; 1985 )

Previous studies has shown that for a weighted undirected graph having $n$
vertices and $m$ edges, a minimal weight spanning tree can be found with
$O^{*}\bigl{(}\sqrt{mn}\bigr{)}$ calls to the weight oracle. The present note
shows that a given spanning tree can be verified to be a minimal weight
spanning tree with only $O\bigl{(}n\bigr{)}$ calls to the weight oracle and
$O\bigl{(}n+\sqrt{m}\log n\bigr{)}$ total work.

quantum algorithms, graph theory, spanning tree

††support: Disclaimer. All statements of fact, opinion, or analysis expressed
in this paper are solely those of the author and do not necessarily reflect
the official positions or views of the Office of the Director of National
Intelligence (ODNI), the Intelligence Advanced Research Projects Activity
(IARPA), or any other government agency. Nothing in the content should be
construed as asserting or implying U.S. Government authentication of
information or ODNI endorsement of the author’s views.

## Introduction

### Problem Statement

The determination of a minimal weight spanning tree of a weighted undirected
graph is a central problem in computational graph theory and a number of well
known classical algorithms address the problem quite efficiently. This problem
has also shown up in the realm of quantum algorithms and the paper [DHHM]
provides nearly matching upper and lower bounds for the problem. (The term
“nearly matching” as used here means that the upper and lower bounds agree to
withing a power of the logarithm of the problem size.) The algorithm in [DHHM]
uses some of the constructs that occur in the classical minimal spanning tree
algorithms, along with a somewhat sophisticated version of the quantum minimum
algorithm (which itself is based on Grover’s algorithm).

A closely related problem deals with the verification of minimal spanning
tree. In this formulation of the problem, both a weighted graph and a spanning
tree of that graph are given as inputs, and the problem is to decide whether
the given spanning tree is of minimal weight (and if not to give a lower
weight spanning tree). Based on work of [Ko], a simple classical verification
algorithm was given in [Ki].

###### Problem

Given a graph $G=(V,E)$ consisting of $n={\left|{G}\right|}$ vertices and
$m={\left|{E}\right|}$ edges along with a weight function on the edges
$w:\,E\rightarrow{\mathbb{R}}^{+}$, and a spanning tree $T=(V,F)$ with
$F\subset E$ and ${\left|{F}\right|}=n-1$, verify that $T$ is a minimal weight
spanning tree.

The goal of this paper is to develop a quantum algorithm for the verification
problem. We build heavily on the graph theory methods given in [Ki] and
[KPRS]. Our quantum tool in this case is a fairly simple version of Grover’s
algorithm. Nevertheless we are able to show that verification is simpler than
finding the solution ab initio.

### Computational Models

There is a basic question of how the graphs $G$ and $T$ are presented, and
this can critically affect the efficiency of the algorithm. A graph can be
presented by an adjacency matrix or by a simple listing of its edges (and this
may be either a sorted or an unsorted list).

In the classical world, the problem statement is fairly simple. In the quantum
world, the graph is presented to the algorithm as an oracle, and the
complexity of the algorithm is measured in the number of oracle calls
necessary to solve the problem.

Oracles can be applied in the classical world, as well, but they are less
indicative of the computational complexity of the problem than in the quantum
world. In the classical world, the entire graph needs to be made available to
the algorithm, so in the adjacency matrix model there would be
$O\bigl{(}n^{2}\bigr{)}$ calls to the oracle specifying the graph, while in
the edge list model there would be $m$ calls to the oracle simply to get the
entire graph into the computer.

There also has to be an oracle that gives the weight of an edge, and in the
adjacency matrix model or the edge list model, there would be $m$ calls to the
weight oracle. It is useful to combine the graph oracle with the weight
oracle. In the adjacency matrix model, the graph is extended to a complete
graph and weight $+\infty$ is assigned to all non-graph edges, with the oracle
being given as a function $w:\,V\times
V\rightarrow{\mathbb{R}}^{+}\cup\\{\infty\\}$. In the edge list model the
oracle is a function, $e:\,[1,m]\rightarrow V\times V\times{\mathbb{R}}^{+}$
where the first two components give the endpoints of the $i^{\hbox{\sevenrm
th}}$ edge of the graph $G$ and the last component gives the weight of that
edge.

In this note, we consider both of these models, but from the quantum
perspective, the oracle has to be viewed as a reversible function that then
operates on quantum states. The two models to be considered here are:

(1) There is the weight oracle in the adjacency matrix model. For this model,
a call to the quantum weight oracle is
${\mid{a,b,x}\rangle}\rightarrow{\mid{a,b,x\oplus w(a,b)}\rangle}$ where
$a,b\in V$ are a pair of vertices. (Note that $x$ here is just some arbitrary
initial bit string.) For finding minimum weight spanning trees, this is bad if
the graph is moderately sparse. For checking the minimality of a spanning
tree, the input would consist of a simple listing of the edges and would be of
length $n-1$.

(2) There is the combined edge list and edge weight in the edge list model.
For this model, a call to the quantum oracle is
${\mid{i,x,y,z}\rangle}\rightarrow{\mid{i,x\oplus a,y\oplus b,z\oplus
w}\rangle}$ where $a,b\in V$ are a pair of vertices such that $(a,b)$ is the
$i^{\hbox{\sevenrm th}}$ edge of the graph $G$ and $w=w(a,b)$ is its weight.
(Note that $x$, $y$, and $z$ here is just some arbitrary initial bit strings.)

Note that the result for model (1) above will give an upper bound for model
(2), but both models will be considered in this note. Thus in the adjacency
matrix model, there will be a weight oracle given $w:\,V\times
V\rightarrow{\mathbb{R}}^{+}\cup\\{+\infty\\}$ and the spanning tree to be
checked for minimality will be (classically) input as a list of edges
$T=\bigl{\\{}(a_{1},b_{1}),(a_{2},b_{2}),\ldots,(a_{n-1},b_{n-1})\bigr{\\}}$
with $(a_{i},b_{i})\in V\times V$ for $i=1,\ldots,n-1$. We will also consider
the $e$ oracle in the edge list model. However, even there, the spanning tree
to be checked for minimality will still be classically input as a list of
edges, only now the spanning tree to be checked for minimality will be
(classically) input as a list of edge indices $T=\bigl{\\{}e_{i},e_{2}\,\ldots
e_{n-1}\bigr{\\}}$ with $e_{i}\in[1,m]$.

In both of the above formulations, the subtree to be tested for minimality by
the quantum algorithm is input classically. This gives a lower bound for the
complexity of the quantum algorithm of $O(n)$, since the algorithm has to at
least read in all the (classical) input. However, there are other possible
statements of the problem.

(3) Given an oracle for the weights of $G$ (which is by default, also an
oracle for querying whether a given pair of points of $V$ is an edge of $G$),
the input could be by an oracle for the putative minimal spanning tree. Thus,
in the adjacency matrix model, there is a function $mst:V\times
V\rightarrow\\{0,1\\}$ where $mst(a,b)=1$ if $(a,b)$ is an edge in $T$ and
$mst(a,b)=0$ if $(a,b)$ is not an edge in $T$, while in the edge list
model,there is a function $mst:V\times[1,m]\rightarrow\\{0,1\\}$ where
$mst(i)=1$ if $i$ is an edge index in $T$ and $mst(i)=0$ if $i$ is not an edge
in $T$. In either case, the problem then becomes to determine whether $mst$ is
a correct oracle. The complication is that there are now two oracles to count
calls to, and in principle there could be an operation curve of tradeoffs.

In fact, this is almost certainly the case, because on one extreme the minimal
spanning tree can be found simply by computing it with a quantum algorithm and
then checking the $mst$ oracle for mismatches with the minimal spanning tree
found. This reduces to the problem: Given a set $S$ and a subset $U\subset S$
and a (quantum) oracle $p:\,S\rightarrow\\{0,1\\}$, is it the case that
$p(s)=1$ if and only if $s\in U$? Counting oracle calls here would seem to be
a simple application of Grover’s algorithm.

## Minimal Weight Spanning Trees

### Checking a Spanning Tree

The key observation from [Ki] is the following. For a graph $G=(V,E)$ and any
spanning tree $T$ of $G$, there is a unique path between any two edges $u,v\in
V$. $T$ is a minimal weight spanning tree if and only if the weight of each
edge $(u,v)\in E-T$ is greater than or equal to the the heaviest edge in the
path in $T$ between $u$ and $v$. What is needed is an easy way to find the
weight of the heaviest edge in the path in $T$ between $u$ and $v$.

The idea for checking a putative spanning tree $T$ for minimality is to show
that for any other edge of $G$ not in $T$, in the cycle formed by including
this edge, the highest weight edge in the cycle is exactly this edge. There is
no way that this edge can be part of a minimum weight spanning tree.

This is to be checked for all edges of $G$, so by invoking Grover’s algorithm
in the quantum setting, the total work is $O\bigl{(}\sqrt{m}\bigr{)}$ times
the work of checking an edge. The problem is that for checking an edge
$(u,v)\in E-T$, the length of the path in $T$ between $u$ and $v$ could be
very large, perhaps even as big as $n-1$, so even using Grover’s algorithm to
find the maximal weight edge on this path is not adequately efficient.

### Boruvka Trees

What is needed is a a new data structure that allows the maximal weight edge
on any path in $T$ to be found efficiently. The basic idea for this comes from
one of the earliest papers in computational graph theory [B], that was the
forerunner of several modern spanning tree algorithms. The key properties of
the Boruvka tree built from a putative minimal spanning tree come from [Ki]
and will be summarized here without proof.

The idea of a Boruvka tree built from a spanning tree $T$ is that $B_{T}$ is a
tree whose leaves are the vertices $V$ and whose internal nodes are to be
viewed as subsets of $V$.

In general for any graph $G=(V,E)$ and any spanning tree $T$ of $G$, the
Boruvka graph is a rooted tree of depth at most
$\lceil\log_{2}({\left|{V}\right|})\rceil$. This Boruvka graph consists of
successively larger aggregations of elements of $V$. All nodes in a Boruvka
tree are subsets of $V$. The leaves are all the singleton sets $\\{v_{i}\\}$
as $v_{i}$ runs over all the elements of $V$, and eventually the root is
formed, which will be $V$ itself. Any intermediate node in a Boruvka tree is
the union of its children.

A Boruvka tree is built from the bottom up. At each stage or level, every node
computes its nearest neighbor (i.e. the node that it is closest to), and an
edge is formed for all such nodes. The nodes of the next level up are then the
connected components of the graph of the previous level. The weight of each
branch is just the weight of the edge of $G$ that was just added. The result
is a rooted tree with at most $2\,n$ nodes and $n$ leaves.

The key property of $B_{T}$ is that if $u,v\in V$ are a pair of vertices and
if $B_{T}(u,v)$ is the smallest subtree of $B_{T}$ that has both $u$ and $v$
as leaves, then the weight of the heaviest edge that connects $u$ and $v$ in
the original spanning tree $T$ is equal to the weight of the heaviest edge in
$B_{T}(u,v)$. The Boruvka tree $B_{T}$ is a full branching tree, which means
that it has a specified root, all its leaves are at the same level, and each
internal node has at least two children.

The height of $B_{T}$ is at most $\lceil\log_{2}n\rceil$. Therefore once
$B_{T}$ has been constructed, finding the heaviest edge in $B_{T}(u,v)$ costs
at most $O\bigl{(}\log n\bigr{)}$ operations. In fact, if $B_{T}$ has already
been built, then finding the heaviest edge in $B_{T}(u,v)$ requires no queries
of the edge weight oracle. Therefore, to check any edge in the original graph
requires only one oracle query, and total work at most $O\bigl{(}\log
n\bigr{)}$.

## The Quantum Algorithm

The Boruvka tree $B_{T}$ can be made with work $O\bigl{(}n\bigr{)}$, (not just
$O\bigl{(}n\log n\bigr{)}$ work), and can be done classically (see [Ki] and
[Ko]), the total number of oracle queries of the weight function being
$O\bigl{(}n\bigr{)}$, as well. This is what makes this algorithm so effective.
Once the Boruvka tree of the input spanning tree has been formed, it is
possible to check whether the input spanning tree is minimal.

To check any edge $(a,b)\in E$ from the original graph $G$, the maximal weight
of the edge in the path in $T$ that connects $a$ and $b$ is easily found.
Simply start with the leaves $a$ and $b$ and go up $B_{T}$ one level at a time
until they meet at a common internal node (which might be the root). Recording
the maximal weight found in the set of edges traversed in $B_{T}$ up the their
common internal node gives the maximal weight of the edge in the path that
connects $a$ and $b$. Since the height of $B_{T}$ is bounded by
$\lceil\log_{2}n\rceil$, the total work for this is $O\bigl{(}\log n\bigr{)}$,
and no oracle calls are required since $B_{T}$ is already built classically.
To check if $(a,b)$ is of lower weight than the maximal weight of the edge in
the path in $T$ that connects $a$ and $b$ only require one invocation of the
weight oracle. Of course, if this weight is less, then a lower weight spanning
tree than $T$ has been found by swapping out the maximum weight edge in the
path that connects $a$ and $b$ in $T$ with the edge $(a,b)$.

Using Grover’s algorithm over all vertex pairs $V\times V$ for the weight
oracle, therefore requires $O\bigl{(}n\bigr{)}$ oracle queries, and
$O\bigl{(}n\log n\bigr{)}$ total work.

If an edge weight oracle is given, then it is possible to run Grover’s
algorithm over the original edge set $E$, which only requires
$O\bigl{(}\sqrt{m}\bigr{)}$ oracle queries, and $O\bigl{(}\sqrt{m}\log
n\bigr{)}$ total work. Since $m<n^{2}$, it follows that the number of oracle
queries for the quantum part of the algorithm is less than the number of
classical oracle queries needed to construct $B_{T}$. Therefore the total
number of oracle queries is $O\bigl{(}n\bigr{)}$ and the total work is
$O\bigl{(}n+\sqrt{m}\log n\bigr{)}$.

In conclusion, it is interesting that the verification of a putatively correct
answer can be accomplished with considerably less work than that of finding
the answer.

## References

  * B Otakar Borűvka, O jistém problému minimálním (About a certain minimal problem), Práca Moravské Pr̆írodoc̆edecké Spolec̆nosti 3, 37-58 . (in Czech, with German summary)
  * DHHM Christoph Dürr, Mark Heiligman, Peter Høyer, and Mehdi Mhalla, Quantum query complexity of some graph problems, SIAM Journal on Computing 35(6), 1310–1328 , see also http://xxx.lanl.gov/abs/quant-ph/0401091.
  * Ki Valerie King, A simpler minimum spanning tree verification algorithm., Algorithmica 18, 263-270 .
  * KPRS V. King, C.K. Poon, V. Ramachandran, and S. Sinha, An optimal EREW PRAM algorithm for minimum spanning tree verification., Information Processing Letters 62, 153-159 .
  * Ko Komlos, Linear verifcation for spanning trees, Combinatorica 5, 57-65 .


# Sensitive single-photon test of extended quantum theory with 2D hexagonal
boron nitride

Tobias Vogl<EMAIL_ADDRESS>Institute of Applied Physics, Abbe Center
of Photonics, Friedrich-Schiller-Universität Jena, 07745 Jena, Germany
Cavendish Laboratory, University of Cambridge, JJ Thomson Avenue, Cambridge
CB3 0HE, United Kingdom  Heiko Knopf  Institute of Applied Physics, Abbe
Center of Photonics, Friedrich-Schiller-Universität Jena, 07745 Jena, Germany
Fraunhofer-Institute for Applied Optics and Precision Engineering IOF, 07745
Jena, Germany  Max Planck School of Photonics, 07745 Jena, Germany  Maximilian
Weissflog  Institute of Applied Physics, Abbe Center of Photonics, Friedrich-
Schiller-Universität Jena, 07745 Jena, Germany  Max Planck School of
Photonics, 07745 Jena, Germany  Ping Koy Lam  Centre for Quantum Computation
and Communication Technology, Department of Quantum Science, Research School
of Physics and Engineering, The Australian National University, Acton ACT
2601, Australia  Falk Eilenberger  Institute of Applied Physics, Abbe Center
of Photonics, Friedrich-Schiller-Universität Jena, 07745 Jena, Germany
Fraunhofer-Institute for Applied Optics and Precision Engineering IOF, 07745
Jena, Germany  Max Planck School of Photonics, 07745 Jena, Germany

###### Abstract

Quantum theory is the foundation of modern physics. Some of its basic
principles, such as Born’s rule, however, are based on postulates which
require experimental testing. Any deviation from Born’s rule would result in
higher-order interference and can thus be tested in an experiment. Here, we
report on such a test with a quantum light source based on a color center in
hexagonal boron nitride (hBN) coupled to a microcavity. Our room temperature
photon source features a narrow linewidth, high efficiency, high purity, and
on-demand single-photon generation. With the single-photon source we can
increase the interferometric sensitivity of our three-path interferometer
compared to conventional laser-based light sources by fully suppressing the
detector nonlinearity. We thereby obtain a tight bound on the third-order
interference term of $3.96(523)\times 10^{-4}$. We also measure an
interference visibility of 98.58% for our single-photons emitted from hBN at
room temperature, which provides a promising route for using the hBN platform
as light source for phase-encoding schemes in quantum key distribution.

2D materials, on-demand single-photons, quantum interferometry, fundamental
test of physics, higher-order interference

##  I Introduction

Low-dimensional materials and nanostructures have gained significant attention
in recent years due to the rich physics and unique properties they offer Wang
_et al._ (2008); Talapin and Shevchenko (2016); Garnett  _et al._ (2019). Of
particular interest are two-dimensional (2D) materials Allen  _et al._ (2010);
Manzeli  _et al._ (2017), which can form topological insulators Xu  _et al._
(2018) or Dirac semimetals Wang  _et al._ (2015) and can exhibit properties
like super-transport Sharma  _et al._ (2020), strongly bound excitons at room
temperature Mak  _et al._ (2010), or superconductivity Cao  _et al._ (2018).
This results in a broad variety of potential applications, including
atomically-thin electronics Radisavljevic  _et al._ (2011), sensing
Smolyanitsky  _et al._ (2016); He  _et al._ (2012), space instrumentation Vogl
_et al._ (2019a), and photonics Liu  _et al._ (2017).
2D materials and their phenomena are governed by quantum physics, which
revolutionized everyday life. Some of the basic principles of quantum theory,
however, are based solely on axioms and postulates. One example for such
fundamental principle based on a postulate is the definition of quantum
mechanics on a complex Hilbert space. Another example is Born’s rule: the
probability density $p\left(\vec{r},t\right)$ of finding a quantum object at
place $\vec{r}$ and time $t$ is given by the absolute square of its wave
function $|\psi\left(\vec{r},t\right)|^{2}$. In Max Born’s original paper this
was just mentioned in a footnote Born (1926), yet it is now a basic foundation
of quantum mechanics. The theoretical framework of quantum mechanics, however,
does not require this to be true Mould (2005). There have been efforts to
derive Born’s rule from more fundamental principles with an operational
approach Saunders (2004), using quantum logic Gleason (1957); Cooke  _et al._
(1985), or recently only making assumptions on the mathematical structure of
the measurement process in quantum mechanics Masanes  _et al._ (2019).
Nevertheless, every approach still needs a certain level of postulation that
needs to be validated.
Any deviation from such postulates manifests in consequences that could be
observed in experiments. A deviation from Born’s rule leads to higher-order
interference Sorkin (1994) and in a hyper-complex Hilbert space phases would
not necessarily commute anymore Peres (1979). There have been several
experimental tests of these extended quantum theories, reducing the upper
bound of any potential deviation successively. Hyper-complex quantum mechanics
has been tested with non-relativistic neutrons Kaiser  _et al._ (1984) and
relativistic photons Procopio  _et al._ (2017). Higher-order interference has
been ruled out using multi-path interferometers Sinha  _et al._ (2010);
Söllner  _et al._ (2012); Kauten  _et al._ (2017); Pleinert  _et al._ (2020a,
b). A common problem of past experiments is they require careful
characterization of a complex measurement apparatus to attain significant
accuracy. Noise and systematic errors in the light source or detector can lead
to an apparent deviation. Moreover, the uncertainty in the characterization of
the measurement apparatus always propagates into an uncertainty of the
observable in question. The ultimate limits to the error are the quantum
fluctuations of the light source (shot noise) and the nonlinear response of
the photodetectors Kauten  _et al._ (2017). It is possible to reduce the
relative quantum fluctuations by increasing the intensity, but this also
increases the nonlinearity of the detector, meaning both effects compete
against each other in a classical design conflict.
An ideal single-photon source (SPS) could resolve both issues: it is not shot
noise-limited, i.e. it has no intensity fluctuations and consecutive single-
photons can be spaced in time such that the detector response can be ensured
to be linear. For a single-photon avalanche diode (SPAD), the pulse period of
the photons must be chosen larger than the detector deadtime.
In this article we use a quantum light source based on a defect center in 2D
hexagonal boron nitride (hBN) coupled to a microcavity Vogl  _et al._ (2019b)
to test for higher-order interference. The resonator improves both the
spectral and photon purity, as well as ensures a high collection efficiency of
the single-photons. We test for higher-order interference with a three-path
interferometer with which we can determine all contributing terms to the
third-order interference individually. We show that using our single-photon
source we can fully circumvent the detector nonlinearity and obtain a tight
bound for the higher-order interference. We also determine the intrinsic
interferometer visibility of our photon source.

##  II Results

Figure 1: Third-order interference $\kappa$ for realistic light sources and
detectors assuming Born’s rule. (a) The shot noise limit of a laser at low
photon rates results in a large uncertainty and for high rates the detector
nonlinearity leads to a deviation from $\kappa=0$. An ideal single-photon
source is not affected by these effects. (b) Evolution of the nonlinearity-
corrected $\kappa$ for different detector deadtime characterization results.
The model assumes the true value to be $\overline{\tau}$ (our measured mean).
(c) Evolution of $\kappa$ for a constant and a realistic rate-dependent
deadtime model.

###  II.1 Theoretical treatment of quantum interference

Quantum interference always occurs between pairs of paths (second-order
interference) and there is no third-order interference. This is a direct
consequence of the linearity of the underlying Hilbert space in quantum
mechanics and the square-relation of Born’s rule. Any deviation from Born’s
rule leads to higher-order interference. In Appendix A we follow R. Sorkin’s
theoretical treatment of quantum interference Sorkin (1994) to calculate the
experimentally accessible quantity $\kappa$, which is the ratio of third-order
interference to expected second-order interference. The parameter can be
measured with a three-path interferometer and is given by

$\displaystyle\kappa=\frac{\epsilon}{\delta}$

where the numerator

$\displaystyle\epsilon=R_{ABC}-R_{AB}-R_{AC}-R_{BC}+R_{A}+R_{B}+R_{C}-R_{0}$

is the third-order interference term and the denominator

$\displaystyle\begin{gathered}\delta=\left\lvert
R_{AB}-R_{A}-R_{B}+R_{0}\right\rvert+\left\lvert
R_{AC}-R_{A}-R_{C}+R_{0}\right\rvert\\\ +\left\lvert
R_{BC}-R_{B}-R_{C}+R_{0}\right\rvert\end{gathered}$

is the sum of the second-order interference terms. The photon rates $R_{i}$
are the detected rates when the $i$th path(s) of the interferometer are open
and $i=0$ corresponds to all paths closed. This parameter describes the
deviation from Born’s rule and allows us to compare the results from different
experiments. It is worth noting the third-order interference term vanishing
implies that all other higher orders vanish as well Sorkin (1994). In order to
measure $\kappa$, each path of the interferometer must be able to open and
close individually.

###  II.2 Realistic measurement apparatus

As already mentioned, an imperfect measurement apparatus can lead to apparent
higher-order interference. In Fig. 1(a) we simulate how $\kappa$ evolves as a
function of the incident photon rate into the three-path interferometer for an
ideal coherent state source (laser) and an ideal SPS. To simulate a (shot
noise-limited) coherent state source, we perform Monte Carlo simulations and
average over a sample size of $N=10^{4}$ (for each rate). To model the
nonlinearity, a detector deadtime of 45 ns has been assumed (see Appendix B
for the nonlinear model). The sample size $N$ was chosen such that the mean
value of $\kappa$ does not significantly change when increasing the sample
size to $N+1$:

$\displaystyle\frac{1}{N}\sum_{i}^{N}\kappa_{i}-\frac{1}{N+1}\sum_{i}^{N+1}\kappa_{i}\ll
1$

For low photon rates shot noise dominates and the uncertainty of $\kappa$
(standard deviation over all simulation runs) is large, thus providing only a
weak upper bound on the third-order interference. When averaging over a large
sample, the mean value can be estimated better, the large uncertainty,
however, will remain. It should be noted that the bias of $\kappa$ in the low
photon rate limit is a systematic error also caused by shot noise (see
Appendix C for the full explanation). As the photon rate increases, the
relative intensity fluctuations decrease and consequently also the uncertainty
of $\kappa$, but eventually the detector nonlinearity leads to an apparent and
systematic deviation from $\kappa=0$. With an ideal SPS one would find
$\kappa=0$ for all photon rates. While shot noise is not present in an ideal
SPS, the detector deadtime can contribute towards a finite $\kappa$.
Nevertheless, by adjusting the time interval of consecutive single-photons,
this effect can be prevented. It is worth noting that the data in Fig. 1(a)
for both light sources has not been corrected for the detector nonlinearity.
While a single-photon source does intrinsically not require such correction,
for the coherent state source this is attempted in the following.
To account for this systematic error for the coherent state source, the
deadtime must be known, however, this requires an accurate characterization.
Furthermore, it is important that this measurement does not rely on
interference, otherwise any higher-order interference term would already
influence this characterization. We have characterized our SPADs (ID Quantique
ID100) with the superposition method Kauten  _et al._ (2014) (see Appendix B)
and found a deadtime of $\tau=43.56(143)$ ns. We have used the standard
deviation of multiple measurement repetitions as the uncertainty. The question
arises how such uncertainty propagates into $\kappa$. For the following model
we assume for simplicity that our measured mean value of 43.5 ns is the true
detector deadtime. In general this will not be the case, since approximating
the mean exactly takes infinite measurements. We then calculate the
nonlinearity-corrected $\kappa$ for the potential characterization results
$\tau_{1}=41.0$, $\tau_{2}=43.5$, and $\tau_{3}=45.0$ ns, corresponding to our
measured mean $\pm$ one standard deviation, respectively. As shown in Fig.
1(b), even after the correction, the uncertainty leads again to an apparent
and systematic third-order interference strength on the order of 1% of the
second-order interference for photon countrates exceeding $10^{6}$ s-1. This
is possibly a limiting factor in a previous experiment Söllner  _et al._
(2012).
In addition to the potentially inaccurate characterization, the detector
deadtime is countrate-dependent and becomes shorter near saturation. This is
due to a charge/discharge of a fixed RC circuit and a comparator with a set
threshold in the detector. When the countrate increases, the RC circuit cannot
fully charge/discharge, resulting in a slight decrease of the deadtime. This
makes an accurate characterization impractical. To illustrate this countrate-
dependency of the deadtime, we have repeated the characterization of the SPADs
with the superposition method for different photon countrates. Of course, each
measurement for each photon countrate has now its own uncertainty, propagating
into an uncertainty of our extracted rate-dependent model. For the following
we again assume our model describes the true nonlinear behavior of the
detector, but in general this is not the case. When correcting $\kappa$ with
the rate-dependent deadtime (for the rate-dependent deadtime model see
Appendix B) there is of course no deviation (see Fig. 1(c)), but when we
correct with a constant deadtime, this leads to a value for $\kappa$ on the
order of $10^{-3}$. This is, in fact, also the current state-of-the-art in the
quantum regime Kauten  _et al._ (2017). It should be noted that even the
correction of the rate-dependent deadtime with a constant deadtime yields
$\kappa=0$ for a rate of 1.55 MHz. This is due to the fact that the constant
deadtime is the correct deadtime for one particular rate and hence there is a
combination of rates which yields $\kappa=0$. We note that the input rate at
which this happens cannot be estimated accurately, as this requires accurate
characterization of the deadtime and if this was possible, accurate deadtime
correction could be employed in the first place. Furthermore, the detector
deadtime characterization using the superposition method is also wavelength
dependent, making an accurate characterization even more difficult (see
Appendix B).
Using a true single-photon source or quantum emitter, these problems can be
circumvented completely. For a sufficiently low second-order correlation
function $g^{(2)}\left(0\right)$ and high enough quantum efficiency, the
quantum light source beats the shot noise limit and each single-photon pulse
contains one and only one photon, i.e. there are no fluctuations. Moreover,
spacing the photons longer in time than the detector deadtime makes the
detector response perfectly linear. The latter can be easily achieved by
pulsed single-photon generation and choosing a pulse period longer than the
deadtime. For our detector this limits the maximal incident rate to 20 to 25
MHz. This of course implies that preventing the deadtime only works up to a
maximal photon rate, however, this maximum is anyway the detection limit of
the specific detector due to the deadtime. In other words, with the single-
photon source the nonlinearity can be prevented over the entire dynamic range
of the detector. Alternatively, when the excited state lifetime of the quantum
emitter is much longer than the deadtime, the single-photon source could also
be excited continuously.

###  II.3 Quantum light source

Our quantum light source is based on a color center in hBN, which is an
intensively researched single-photon emitter system due to its superior
brightness Tran  _et al._ (2016a, b); Vogl  _et al._ (2017), purity Vogl  _et
al._ (2018), and quantum efficiency Nikolay  _et al._ (2019) at room
temperature. In addition, the emitters can have near-ideal out-coupling
efficiency, with no photons lost due to total internal or Fresnel reflection
Vogl  _et al._ (2019c). Recent results suggest the quantum emission in the
visible spectrum is carbon-related Mendelson  _et al._ (2020). Long-time
characterizations proved their reliability Vogl  _et al._ (2018); Liu  _et
al._ (2020), allowing us to use the emitter for the extended quantum theory
test. While there has been a lot of research into the creation Chejanovsky
_et al._ (2016); Choi  _et al._ (2016), characterization Dietrich  _et al._
(2018), and tuning of the emitters Noh  _et al._ (2018); Mendelson  _et al._
(2019), applications are still sparse. So far, there has been quantum random
number generation White  _et al._ (2020) and nanothermometry Chen  _et al._
(2020) based on single-photon emitting hBN.
To increase the spectral and photon purity, as well as the collection
efficiency, we have coupled our emitter to a plano-concave microcavity (for
details see Ref. Vogl  _et al._ (2019b)). The defect is excited off-resonantly
outside the stopband of the cavity with an ultrashort pulse laser at 470 nm
where the cavity is transparent for the excitation. We have used the second-
harmonic of a tunable Ti:sapphire laser at a repetition rate of 80.136 MHz. We
estimate the pulse length of the second-harmonic to be well below 200 fs. This
ultrashort pulse length guarantees that there is no double-excitation during a
single laser pulse (the probability for a double-excitation is $5\times
10^{-4}$ at full saturation). The single-photon linewidth is 224 pm (FWHM) at
a center wavelength of 565 nm. The center wavelength can be tuned by adjusting
the cavity length within the free-space emission linewidth of the emitter,
which is 5.76 nm (FWHM). The second-order correlation function as shown in
Fig. 2(a) reveals a very high photon purity with
$g^{(2)}\left(0\right)=6.4\times 10^{-3}$ after background correction and in
the linear power limit. The single-photons are linearly polarized and are
separated from the excitation laser by a dichroic mirror and an additional
band-pass filter. The single-photon source provides two fiber output ports
after a beamsplitter, one for a locking loop to keep the cavity resonant with
the emitter and the other guiding the photons to the actual experiment into
the interferometer. The entire light source is fully self-contained within a
volume less than 1 liter and weighs 595 g (including housing, all optics,
electronics, and an onboard computer for tuning of the source). This does not
include the ultrashort pulse laser and second-harmonic stage used for
excitation, however, the light source is also equipped with a CW laser which
is included within the volume. A photograph of the integrated light source can
be found in Fig.2(b). The excitation laser can be switched by connecting a
single-mode fiber.

Figure 2: Experimental setup and results. (a) Second-order correlation
function recorded with pulsed excitation. The data has been centered around
zero time delay and normalized. Integration over the peaks and the same area
around zero yields $g^{(2)}\left(0\right)=6.4\times 10^{-3}$ after background
correction. (b) Photograph of the integrated quantum light source mounted in a
1U CubeSat structure. (c) The polarization of the photons from the fiber-
coupled single-photon source (FC-SPS) is rotated with half-wave plate (HWP)
and additionally filtered by a polarizing beamsplitter (PBS). A quarter-wave
plate (QWP) rotates the polarization to left-circular. A diffractive optical
element (DOE) splits the photon amplitude into three equal ones. A concave
mirror (CM) retroreflects the photons which recombine at the DOE and exit the
PBS on the reflective port (due to the phase shift of the reflection at the
CM), where the photons are detected by a SPAD. The forward/reflected
propagation direction is marked with green/red arrows. A shutter array (SA)
can be moved through the paths, allowing us to open/close each path (A, B, C)
individually. The phase shifters (PS) are optional for the determination of
the interference visibility. (d) Measurement repetitions of $\kappa$. The mean
value of 5000 runs is $3.96\times 10^{-4}$ (red line) and the standard
deviation is $5.23\times 10^{-4}$ (green lines). These values have been
determined from fitting a normal distribution to the histogram (on the right).
For the sake of clarity, the data shown here has been downsampled by a factor
of 11.

###  II.4 Testing for higher-order interference

We now turn to the measurement of $\kappa$. The experimental setup for the
higher-order interference test is shown in Fig. 2(c): the single-photons from
our quantum light source are guided by a fiber to the interferometer. While
the single-photons as emitted by the cavity are linearly polarized, the fiber
rotates this polarization by a random but fixed angle. Using a half-wave plate
and a polarizing beamsplitter (PBS), this polarization is reset to linear
vertical polarization and then with a quarter-wave plate (QWP) angled at -45∘
to left-circular polarization. The photon wave is split into three amplitudes
of equal strength by a $1\times 3$ diffractive grating beamsplitter (see
Appendix D). The light in each path is retroreflected by a concave silver
mirror ($R=100$ mm) and then recombines back at the grating. Using a concave
mirror ensures equal path lengths by default and hence also operation in an
interference maximum. This in turn reduces the influence of phase instability
in the measurements. As the phase shift induced by the mirror exchanges left-
and right-handed circular polarization, the reflected photons are horizontally
polarized after the QWP and thus exit the initial PBS on the reflective port.
Finally, a single-photon avalanche diode detects the photons. The initial
alignment of the setup was done using a 561 nm laser system with a coherence
length exceeding 100 m.
The separation angle after the grating is $8.08^{\circ}$ and a mask moved
through the beams allows us to block each path individually. To gather large
statistics, we have mounted the blocking mask on a fast motorized stage
(Thorlabs DDS220) and automated the entire experiment. The large separation
angle ensures a macroscopic distance of the individual paths in the
interferometer (12.5 mm separation at the blocking mask), thus guaranteeing
independence of the paths and preventing any potential crosstalk or
nonclassical paths Sawant  _et al._ (2014); De Raedt  _et al._ (2012).
We first measured the single-photon interference visibility. Depending on the
setting of the mask position, we can emulate three different two-path
Michelson interferometers and one three-path Michelson-type interferometer. To
vary the phases in the interferometer arms, we have used phase plates with a
custom-made anti-reflection coating on both sides (see Appendix E). All phase
plates have been coated within the same coating run to minimize differences
between individual phase plates. Due to the slightly unbalanced splitting
ratios of the grating (see Appendix D), the interference visibilities are
limited, but still theoretically all exceed 99.93% (see Tab. 1). Thus, the
interference visibility can be used to characterize the coherence of the
single-photon source. For details of the theoretical calculations see Appendix
F.
The experimental characterization shows high interference visibilities up to
98.58% (see Tab. 1). To the best of our knowledge, this is the first time that
such interference visibility has been measured for single-photons emitted from
hBN at room temperature. We do note, however, there was a measurement of this
interference visibility for single-photons from cryogenically cooled quantum
emitters at a temperature of 10 K Qian  _et al._ (2020).
In the final experiment we measured $\kappa$ directly. To ensure that the
interferometer is most sensitive to any potential higher-order interference,
the angles of the phase plates were set to the central interference maximum.
Due to the fixed repetition frequency of the ultrashort pulse laser, for this
experiment we replace the excitation with another laser system with a variable
repetition frequency ranging from 2.5 to 80 MHz. To prevent more than one
pulse during the detector deadtime we choose 10 MHz as the excitation
frequency. As already mentioned, the automatization of the experiment allows
us to repeat the experiment many times and record large data sets that we can
average over. The order in which the individual paths were opened and closed
has been randomized for each run to reduce potential systematic errors. We
have used data acquisition times of $1,2,5$ s per configuration without
noticing any significant difference. One specific measurement campaign is
shown in Fig. 2(d), with $\kappa=3.96(523)\times 10^{-4}$, averaged over 5000
runs (corresponding to a total measurement time of 58 hours). The mean and
standard deviation have been obtained by fitting a normal distribution to the
histogram of the measured $\kappa$ values (see Fig. 2(d) on the right). The
mean is marked in red and mean $\pm$ one standard deviation is marked in
green.

Table 1: Theoretical (based on the grating splitting ratios) and experimentally measured interferometric visibilities. The individual paths A, B, and C are labeled in Fig. 2(c). Paths | Theory [%] | Experiment [%]
---|---|---
AB | 99.9429 | 98.56
AC | 99.9369 | 95.17
BC | 99.9998 | 98.58
ABC | 99.9987 | 98.22

##  III Conclusion and outlook

We have tested a fundamental principle of standard quantum theory based on a
postulate experimentally. In particular, we have tested for deviations from
Born’s rule, which would manifest in higher-order interference. We
demonstrated that using a single-photon source based on 2D hexagonal boron
nitride coupled to a resonator, we can effectively circumvent the shot noise
limit and the detector nonlinearity, which have been the limiting effects in
past experiments. Thus, we have been able to get an accurate upper bound to
the amount of higher-order interference, which was $3.96(523)\times 10^{-4}$
compared to the expected second-order interference. For the third-order
interference term in the quantum regime, this upper bound is tighter than the
previous best value of $-1.1(16)\times 10^{-3}$ Kauten  _et al._ (2017). Our
experiment is also the first experiment of this kind utilizing a true single-
photon source (excluding heralded spontaneous parametric down-conversion Sinha
_et al._ (2010); Kauten  _et al._ (2017)).
The quantum light source used in the experiment was already compact and fully
self-contained within a volume of less than 1 liter and a weight of less than
1 kg. The light source therefore fulfills the strict requirement for a 1U
CubeSat, a picoclass satellite standard. It is hence possible to miniaturize
the interferometer and test for higher-order interference in microgravity on a
CubeSat in space. Potential gravitational effects could thus be ruled out as
well.
The quantum light source could also be employed to other tests of quantum
theories beyond the standard model. The same detector nonlinearity effect is
skewing the interference contrast of Mach-Zehnder and Sagnac interferometers
in photonic tests of hyper-complex quantum mechanics. The interference pattern
of these interferometers is of the form of a sine squared (see Appendix F) and
thus requires a high dynamic range of the detectors. Circumventing the
detector nonlinearity and reducing intensity fluctuations could improve the
accuracy of such measurements. This also demonstrates a quantum advantage of
using single-photons for interferometric sensing applications.
Our results also suggest, that the single-photons can be used for phase-
encoding schemes for quantum key distribution (QKD). The quantum bit error
ratio (QBER), the defining metric in QKD, is directly related to the
interference visibility $V$ for phase encoding Gisin  _et al._ (2002):

$\displaystyle\text{QBER}=\frac{1-V}{2}$

The intrinsic limit on the QBER for our photon source is thus 0.709%. This is
important as it has been proven recently that single-photons from hBN can
outperform state-of-the-art weak coherent and decoy protocols for QKD Vogl
_et al._ (2019b). This extends the possible applications of single-photon
sources based on hBN and offers a promising route to versatile optical quantum
technologies with the hBN platform.

## Acknowledgments

We thank Léa Carmagnolle and the ID Quantique team for fruitful discussions on
characteristics of single-photon avalanche diodes. This work was funded by the
Australian Research Council (CE170100012, FL150100019), the Federal Ministry
of Education and Research BMBF (13XP5053A), and by the European Union, the
European Social Funds and the Federal State of Thuringia (2019FGR0101).

##  Appendix A Theoretical treatment of quantum interference

The calculation follows the theoretical treatment of quantum interference by
R. Sorkin Sorkin (1994), which was also used in past experiments Sinha  _et
al._ (2010); Söllner  _et al._ (2012); Kauten  _et al._ (2017). According to
Born’s rule the probability density after $k$ slits is given by

$\displaystyle p=\left\lvert\sum^{k}_{i}\psi_{i}\right\rvert^{2}$ (1)

where we have dropped the spatial and temporal dependence for the sake of
conciseness. Thus, Born’s rule predicts quantum interference occurs only
between pairs of paths and there is no higher-order interference. For a
double-slit experiment with slits $A$ and $B$ we find

$\displaystyle
p_{AB}=\left\lvert\psi_{A}+\psi_{B}\right\rvert^{2}=\left\lvert\psi_{A}\right\rvert^{2}+\left\lvert\psi_{B}\right\rvert^{2}+\psi_{A}^{*}\psi_{B}+\psi_{A}\psi_{B}^{*}$
(2)

The complex cross terms can be defined as the second-order interference term:

$\displaystyle I_{AB}$
$\displaystyle=\psi_{A}^{*}\psi_{B}+\psi_{A}\psi_{B}^{*}=p_{AB}-\left\lvert\psi_{A}\right\rvert^{2}-\left\lvert\psi_{B}\right\rvert^{2}=$
$\displaystyle=p_{AB}-p_{A}-p_{B}$ (3)

Adding more paths to the interferometer, meaning opening more slits, does not
increase the complexity. For example, for three slits the probability
distribution at the detection screen is given by

$\displaystyle p_{ABC}=p_{A}+p_{B}+p_{C}+I_{AB}+I_{AC}+I_{BC}$ (4)

In analogy to the second-order interference term, we can define the third-
order term as

$\displaystyle I_{ABC}$
$\displaystyle=p_{ABC}-(p_{A}+p_{B}+p_{C}+I_{AB}+I_{AC}+I_{BC})=$
$\displaystyle=p_{ABC}-p_{AB}-p_{AC}-p_{BC}+p_{A}+p_{B}+p_{C}$ (5)

Hence, by measuring each contributing term individually it is possible to
measure $I_{ABC}$. In standard quantum theory, we find of course $I_{ABC}=0$.
It is worth noting, if the third-order interference term vanishes, all other
higher orders vanish as well Sorkin (1994). In a practical experiment, the
probabilities are not directly accessible. It is convenient to measure photon
countrates $R_{i}$ (where the $i$th slits are open) instead. These rates are
directly proportional to the probabilities, which yields the parameter

$\displaystyle\epsilon=R_{ABC}-R_{AB}-R_{AC}-R_{BC}+R_{A}+R_{B}+R_{C}-R_{0}$
(6)

Note that each of the seven terms has been corrected for the darkcount rate,
corresponding to all slits being closed. The parameter $\epsilon$ alone is not
very meaningful, as it depends on the incident photon countrate, which is
different for every individual experiment. To compare the parameter to other
experiments, it is common to normalize this third-order interference by the
sum of the expected second-order interference

$\displaystyle\begin{gathered}\delta=\left\lvert
R_{AB}-R_{A}-R_{B}+R_{0}\right\rvert+\left\lvert
R_{AC}-R_{A}-R_{C}+R_{0}\right\rvert\\\ +\left\lvert
R_{BC}-R_{B}-R_{C}+R_{0}\right\rvert\end{gathered}$ (9)

This gives the parameter

$\displaystyle\kappa=\frac{\epsilon}{\delta}$ (10)

that is directly accessible through an experiment. All that is required is a
three-path interferometer where each path can be opened and closed
individually. In this way, each of the eight contributing terms to $\kappa$ in
Eqn. 10 can be measured.

##  Appendix B Characterization of the detector deadtime

The single-photon avalanche diodes have a nonlinear response function of the
form

$\displaystyle R_{\text{det}}=\frac{R_{\text{act}}}{1+\tau
R_{\text{act}}}+R_{0}$ (11)

where $R_{\text{det}}$ is the detected photon countrate, $R_{\text{act}}$ is
the actual incident photon rate, $\tau$ is the detector deadtime, and $R_{0}$
is the dark countrate. For the sake of clarity we have assumed the detector
efficiency to be 100%. The detector deadtime has been characterized using the
superposition method Kauten  _et al._ (2014). It is particularly important
that this characterization is not relying on an interference effect.
Otherwise, any higher-order interference terms would already influence the
deadtime measurement. In the superposition method two lasers with different
wavelengths to prevent interference are combined with a beamsplitter. We have
used a 532 and 561 nm commercial laser system, which have been intensity
stabilized. After the beamsplitter, the light is focused onto the detector.
With a motorized blocking mask prior to the beam combination we can block each
laser individually. To measure the deadtime, all four possible combinations of
blocked/unblocked lasers have to be measured. A linear detector would satisfy

$\displaystyle
R_{\text{det}}^{532+561}=R_{\text{det}}^{532}+R_{\text{det}}^{561}$ (12)

A measurement with a realistic detector, however, will deviate from this by
some residual $r$:

$\displaystyle
R_{\text{det}}^{532+561}-R_{\text{det}}^{532}-R_{\text{det}}^{561}=r$ (13)

To gather sufficient statistics, we have repeated each measurement 100 times.
A simple direct optimization of the minimization condition

$\displaystyle\min\left(\sum_{i}^{N}r_{i}^{2}\right)$ (14)

allows us to extract the detector deadtime using Eqn. 11. We have also varied
the laser powers to measure the deadtime at different photon countrates. The
deadtime $\tau$ decreases with increasing countrate $R$ (see main text):

$\displaystyle\tau\left(R\right)=51.8\text{ ns}-3.333\text{ fs}\times R$ (15)

It should be noted that this model is not valid anymore near saturation, where
the dependency of the deadtime on the countrate becomes sublinear.
It is worth noting that the detection efficiency (which we have set to 100%
for the calculations) in general is wavelength-dependent, leading to an error
when using different wavelengths for the deadtime characterization. The
deadtime is higher at wavelengths where the detector is more efficient: a
photon that is not detected, i.e. a photon that does not trigger an avalanche
is also not switching the detector into its dead-state. According to the
manufacturer, the detection efficiency at 532 nm is 34%, while at 561 nm it is
32%. The overall error we make by assuming a constant efficiency is therefore
rather small.

##  Appendix C Monte Carlo simulations of an ideal coherent state source

It is worth noting that the Monte Carlo simulation (see main text) of the
parameter $\kappa$ (averaged over the entire sample size) for the coherent
state source predicts a deviation from $\kappa=0$ at low photon rates. This is
not a numeric artifact caused by an insufficiently large sample size, but
rather an actual systematic deviation that appears for coherent states. Since
all $R_{i}$ are drawn from a normal distribution one might rightfully assume
that $\epsilon$ (see Fig. 3(a)) and $\delta$ (see Fig. 3(b)) are also normally
distributed. The parameters $\epsilon$ and $\delta$ are not independent from
each other: $\epsilon<0$ is when $\left\lvert-
R_{AB}-R_{AC}-R_{BC}\right\rvert$ is large, however, this implicates that
$\delta$ is large as well. In other words, a small (particularly a negative)
$\epsilon$ gets divided by a large $\delta$, leading to a positive bias of
$\kappa$. This is visualized by the distribution of $\delta$ for the condition
$\epsilon<0$ and $\epsilon>0$ (see Fig. 3(c)). For this particular simulation
presented here, the mean value of all $\epsilon$ is
$\overline{\epsilon}=-0.09222$ and the mean value of all $\delta$ is
$\overline{\delta}=8.361$. However, the mean value of all $\delta$ when
$\epsilon<0$ is $\overline{\delta}\,|\,\epsilon<0=10.28$, while the mean value
of all $\delta$ when $\epsilon>0$ is $\overline{\delta}\,|\,\epsilon>0=6.345$.
Overall, this means that for a coherent state source at low incident photon
rates there is not only a large uncertainty of $\kappa$, but also a systematic
error, both due to shot noise. A single-photon source is not shot noise-
limited, hence there is neither an uncertainty of $\kappa$, nor is there any
systematic deviation from $\kappa=0$ (predicted by standard quantum theory).

Figure 3: Histograms of simulated parameters $\epsilon$ (a) and $\delta$ (b)
for a shot-noise-limited light source at a photon rate of 10 Hz. Even though
these parameters are normally distributed, they are not independent from each
other: the mean value of $\delta$ for the condition $\epsilon>0$ is smaller
(6.345) compared to the mean value of $\delta$ for the condition $\epsilon<0$
(10.28), as can be seen by the yellow and blue histograms in (c),
respectively. This in turn leads to a bias in $\kappa$ when averaging over all
simulations.

##  Appendix D Characterization of the grating

A custom-made diffractive optical beamsplitter (TS-210-562-Y-A) manufactured
by HOLO/OR has been used. The grating is designed to split a monochromatic
beam into three beams without changing any of the incident light
characteristics (such as polarization), except for its power and propagation
direction. The separation angle is 8.08∘ and the grating has an anti-
reflective coating for 562 nm on both sides. We have characterized the grating
transmission efficiency of all orders and compare it to theoretical design
values (see Tab. 2): according to the specification provided by the
manufacturer, the efficiency into the 0th order is 28.65% and 28.35% into the
$\pm 1$st order. Experimentally, we found 29.28%, 28.28%, and 29.30% for the
0th and $\pm$ 1st orders, respectively. We note that the overall transmission
is nearly 100%, i.e. the grating is lossless (within the experimental
accuracy). However, there the amplitudes of higher orders are non-zero. A
polarization-resolved characterization confirmed the polarization
insensitivity within about 0.1%. The data presented in Tab. 2 was measured
with left-circular polarization, the same polarization that was used in the
experiments.

Table 2: Grating efficiency and uniformity. The overall transmission is close to 100%, but there is a finite transmission into higher orders. The uniformity is the standard deviation of the diffraction orders. Order | Theory [%] | Experiment [%]
---|---|---
-1 | 28.35 | 28.28
0 | 28.53 | 29.26
+1 | 28.35 | 29.30
Overall | 85.23 | 86.84
Uniformity | 0.10 | 0.58

##  Appendix E Fabrication of the phase shifters

For the phase plates we have used borosilicate glass of 180 $\mu$m and 1 mm
thickness. All substrates have been polished and chemically cleaned prior to
the coating runs. Anti-refractive coatings were deposited using a Bühler
SyrusPro 1100 via ion-assisted deposition. The surface of the substrates was
pre-treated with a gentle Ar-ion plasma at a flow of 11 sccm using 80 V bias-
voltage for 100 s. This enhances the surface energy of the interface by
cracking bonds of adsorbed hydrogen, thus creating chemically active sites, to
which the subsequently deposited material may crosslink Knopf  _et al._
(2019). Additionally, the pre-treatment provides a further cleaning effect of
the surface. In the next step, we coated the activated surface with a quarter-
wave stack of MgF2 from an electron beam gun at a low deposition rate of 0.35
nm/s. The chamber temperature was increased to 300 ∘C using four ceramic
heaters to ensure a monocrystalline MgF2 layer. After the first coating run,
the substrates were flipped and the procedure is repeated to also coat the
backside. MgF2 was chosen due to its refractive index being in between that of
air and borosilicate glass. The quarter-wave thickness for our single-photon
wavelength is 307.9 nm. A characterization using a spectrophotometer before
and after the coating showed that the reflection losses decreased from 8.39%
to 2.69% at 565 nm.

##  Appendix F Matrix treatment of the interferometers

Ideally, any interferometer has a visibility of unity. Realistically, however,
the splitting ratios might not be mutually equivalent and each path has some
loss, which reduces the interference contrast intrinsically. To characterize
the coherence of a light source using an interferometer, this intrinsic limit
serves as an upper bound the measurement cannot exceed and has to be
calculated.
An interferometer can be easily calculated using the transfer matrix
formalism. The standard Mach-Zehnder interferometer (MZI) contains a
beamsplitter with matrix

$\displaystyle\mathrm{BS}=\begin{pmatrix}\sqrt{1-R}&\mathrm{i}\sqrt{R}\\\
\mathrm{i}\sqrt{R}&\sqrt{1-R}\\\ \end{pmatrix}$ (16)

where $R$ is the reflection coefficient ($T=1-R$) and a matrix

$\displaystyle\mathrm{P}=\begin{pmatrix}L_{1}\mathrm{e}^{\mathrm{i}\phi}&0\\\
0&L_{2}\\\ \end{pmatrix}$ (17)

describing the paths, where $\phi$ is a phase shift and $L_{1,2}$ contains all
losses of each path, respectively. The total MZI can be described by
concatenating the components:

$\displaystyle\mathrm{MZI}=\mathrm{BS}\times\mathrm{P}\times\mathrm{BS}$ (18)

The output arms can be calculated by projecting the input multiplied by the
MZI matrix. For the input

$\displaystyle\ket{\text{in}}=\begin{pmatrix}1\\\ 0\\\ \end{pmatrix}$ (19)

this gives the well-known $\sin^{2}\left(\phi\right)$ interference pattern.
This relation also allows us to model our realistic beamsplitter with
splitting ratios and losses described in Tab. 2, leading to the theoretical
interference visibilities shown in Tab. 1. Note that the MZI is equivalent to
the Michelson interferometer in our experiment with the only difference that
the phase shifter is passed twice, leading to an effective phase of $2\phi$.
For the three-path interferometer the same approach can be used, extended to
the third path. The beamsplitter matrix changes to that of a tritter, which
can be constructed in general by concatenating three beamsplitters Żukowski
_et al._ (1997):

$\displaystyle\begin{gathered}\begin{pmatrix}\sqrt{1-R_{1}}&\mathrm{i}\sqrt{R_{1}}&0\\\
\mathrm{i}\sqrt{R_{1}}&\sqrt{1-R_{1}}&0\\\ 0&0&1\\\
\end{pmatrix}\times\begin{pmatrix}\sqrt{1-R_{2}}&0&\mathrm{i}\sqrt{R_{2}}\\\
0&1&0\\\ \mathrm{i}\sqrt{R_{2}}&0&\sqrt{1-R_{2}}\\\ \end{pmatrix}\times\\\
\begin{pmatrix}1&0&0\\\ 0&\sqrt{1-R_{3}}&\mathrm{i}\sqrt{R_{3}}\\\
0&\mathrm{i}\sqrt{R_{3}}&\sqrt{1-R_{3}}\\\ \end{pmatrix}\end{gathered}$ (21)

where $R_{i}$ are internal reflection coefficients. We calculate these
coefficients numerically such that they represent our experimentally
characterized tritter. The calculation of the three-path interferometer is
then analogous to that of the MZI.

## References

  * Wang  _et al._ (2008) Ding Wang, Pengcheng Song, Changhong Liu, Wei Wu, and Shoushan Fan, “Highly oriented carbon nanotube papers made of aligned carbon nanotubes,” Nanotechnol. 19, 075609 (2008).
  * Talapin and Shevchenko (2016) Dmitri V. Talapin and Elena V. Shevchenko, “Introduction: Nanoparticle Chemistry,” Chem. Rev. 116, 10343–10345 (2016).
  * Garnett  _et al._ (2019) Erik Garnett, Liqiang Mai, and Peidong Yang, “Introduction: 1D Nanomaterials/Nanowires,” Chem. Rev. 119, 8955–8957 (2019).
  * Allen  _et al._ (2010) Matthew J. Allen, Vincent C. Tung, and Richard B. Kaner, “Honeycomb Carbon: A Review of Graphene,” Chem. Rev. 110, 132–145 (2010).
  * Manzeli  _et al._ (2017) Sajedeh Manzeli, Dmitry Ovchinnikov, Diego Pasquier, Oleg V. Yazyev, and Andras Kis, “2D transition metal dichalcogenides,” Nat. Rev. Mater. 2, 17033 (2017).
  * Xu  _et al._ (2018) Su-Yang Xu, Qiong Ma, Huitao Shen, Valla Fatemi, Sanfeng Wu, Tay-Rong Chang, Guoqing Chang, Andrés M. Mier Valdivia, Ching-Kit Chan, Quinn D. Gibson, Jiadong Zhou, Zheng Liu, Kenji Watanabe, Takashi Taniguchi, Hsin Lin, Robert J. Cava, Liang Fu, Nuh Gedik, and Pablo Jarillo-Herrero, “Electrically switchable Berry curvature dipole in the monolayer topological insulator WTe2,” Nat. Phys. 14, 900–906 (2018).
  * Wang  _et al._ (2015) Jinying Wang, Shibin Deng, Zhongfan Liu, and Zhirong Liu, “The rare two-dimensional materials with Dirac cones,” Natl. Sci. Rev. 2, 22–39 (2015).
  * Sharma  _et al._ (2020) Ankur Sharma, Linglong Zhang, Jonathan O. Tollerud, Miheng Dong, Yi Zhu, Robert Halbich, Tobias Vogl, Kun Liang, Hieu T. Nguyen, Fan Wang, Shilpa Sanwlani, Stuart K. Earl, Daniel Macdonald, Ping Koy Lam, Jeffrey A. Davis, and Yuerui Lu, “Supertransport of excitons in atomically thin organic semiconductors at the 2D quantum limit,” Light Sci. Appl. 9, 116 (2020).
  * Mak  _et al._ (2010) Kin Fai Mak, Changgu Lee, James Hone, Jie Shan, and Tony F. Heinz, “Atomically Thin ${\mathrm{MoS}}_{2}$: A New Direct-Gap Semiconductor,” Phys. Rev. Lett. 105, 136805 (2010).
  * Cao  _et al._ (2018) Yuan Cao, Valla Fatemi, Shiang Fang, Kenji Watanabe, Takashi Taniguchi, Efthimios Kaxiras, and Pablo Jarillo-Herrero, “Unconventional superconductivity in magic-angle graphene superlattices,” Nature 556, 43–50 (2018).
  * Radisavljevic  _et al._ (2011) B. Radisavljevic, A. Radenovic, J. Brivio, V. Giacometti, and A. Kis, “Single-layer MoS2 transistors,” Nat. Nanotechnol. 6, 147–150 (2011).
  * Smolyanitsky  _et al._ (2016) Alex Smolyanitsky, Boris I. Yakobson, Tsjerk A. Wassenaar, Eugene Paulechka, and Kenneth Kroenlein, “A MoS2-Based Capacitive Displacement Sensor for DNA Sequencing,” ACS Nano 10, 9009–9016 (2016).
  * He  _et al._ (2012) Qiyuan He, Zhiyuan Zeng, Zongyou Yin, Hai Li, Shixin Wu, Xiao Huang, and Hua Zhang, “Fabrication of Flexible MoS2 Thin-Film Transistor Arrays for Practical Gas-Sensing Applications,” Small 8, 2994–2999 (2012).
  * Vogl  _et al._ (2019a) T. Vogl, K. Sripathy, A. Sharma, P. Reddy, J. Sullivan, J. R. Machacek, L. Zhang, F. Karouta, B. C. Buchler, M. W. Doherty, Y. Lu, and P. K. Lam, “Radiation tolerance of two-dimensional material-based devices for space applications,” Nat. Commun. 10, 1202 (2019a).
  * Liu  _et al._ (2017) Yan Liu, Bannur Nanjunda Shivananju, Yusheng Wang, Yupeng Zhang, Wenzhi Yu, Si Xiao, Tian Sun, Weiliang Ma, Haoran Mu, Shenghuang Lin, Han Zhang, Yuerui Lu, Cheng-Wei Qiu, Shaojuan Li, and Qiaoliang Bao, “Highly Efficient and Air-Stable Infrared Photodetector Based on 2D Layered Graphene–Black Phosphorus Heterostructure,” ACS Appl. Mater. Interfaces 9, 36137–36145 (2017).
  * Born (1926) Max Born, “Zur Quantenmechanik der Stoßvorgänge.” Z. Physik 38, 803–827 (1926).
  * Mould (2005) Richard A. Mould, “Without the born rule,” arXiv:quant-ph/0507170 (2005).
  * Saunders (2004) Simon Saunders, “Derivation of the Born rule from operational assumptions,” Proc.: Math., Phys. Eng. Sci. 460, 1771–1788 (2004).
  * Gleason (1957) Andrew M. Gleason, “Measures on the closed subspaces of a hilbert space,” J. Math. Mech. 6, 885–893 (1957).
  * Cooke  _et al._ (1985) Roger Cooke, Michael Keane, and William Moran, “An elementary proof of gleason’s theorem,” Math. Proc. Camb. Philos. Soc. 98, 117–128 (1985).
  * Masanes  _et al._ (2019) Lluís Masanes, Thomas D. Galley, and Markus P. Müller, “The measurement postulates of quantum mechanics are operationally redundant,” Nature Commun. 10, 1361 (2019).
  * Sorkin (1994) Rafael D. Sorkin, “Quantum Mechanics as Quantum Measure Theory,” Mod. Phys. Lett. A 9, 3119–3127 (1994).
  * Peres (1979) Asher Peres, “Proposed test for complex versus quaternion quantum theory,” Phys. Rev. Lett. 42, 683–686 (1979).
  * Kaiser  _et al._ (1984) H. Kaiser, E. A. George, and S. A. Werner, “Neutron interferometric search for quaternions in quantum mechanics,” Phys. Rev. A 29, 2276–2279 (1984).
  * Procopio  _et al._ (2017) Lorenzo M. Procopio, Lee A. Rozema, Zi Jing Wong, Deny R. Hamel, Kevin O’Brien, Xiang Zhang, Borivoje Dakić, and Philip Walther, “Single-photon test of hyper-complex quantum theories using a metamaterial,” Nat. Commun. 8, 15044 (2017).
  * Sinha  _et al._ (2010) Urbasi Sinha, Christophe Couteau, Thomas Jennewein, Raymond Laflamme, and Gregor Weihs, “Ruling out multi-order interference in quantum mechanics,” Science 329, 418–421 (2010).
  * Söllner  _et al._ (2012) Immo Söllner, Benjamin Gschösser, Patrick Mai, Benedikt Pressl, Zoltán Vörös, and Gregor Weihs, “Testing born’s rule in quantum mechanics for three mutually exclusive events,” Found. Phys. 42, 742–751 (2012).
  * Kauten  _et al._ (2017) Thomas Kauten, Robert Keil, Thomas Kaufmann, Benedikt Pressl, Časlav Brukner, and Gregor Weihs, “Obtaining tight bounds on higher-order interferences with a 5-path interferometer,” New J. Phys. 19, 033017 (2017).
  * Pleinert  _et al._ (2020a) Marc-Oliver Pleinert, Joachim von Zanthier, and Eric Lutz, “Many-particle interference to test born’s rule,” Phys. Rev. Research 2, 012051 (2020a).
  * Pleinert  _et al._ (2020b) Marc-Oliver Pleinert, Alfredo Rueda, Eric Lutz, and Joachim von Zanthier, “Testing quantum theory with higher-order interference in many-particle correlations,” arXiv:2006.09496 (2020b).
  * Vogl  _et al._ (2019b) Tobias Vogl, Ruvi Lecamwasam, Ben C. Buchler, Yuerui Lu, and Ping Koy Lam, “Compact cavity-enhanced single-photon generation with hexagonal boron nitride,” ACS Photonics 6, 1955–1962 (2019b).
  * Kauten  _et al._ (2014) Thomas Kauten, Benedikt Pressl, Thomas Kaufmann, and Gregor Weihs, “Measurement and modeling of the nonlinearity of photovoltaic and geiger-mode photodiodes,” Rev. Sci. Instrum. 85, 063102 (2014).
  * Tran  _et al._ (2016a) T. T. Tran, K. Bray, M. J. Ford, M. Toth, and I. Aharonovich, “Quantum emission from hexagonal boron nitride monolayers,” Nat. Nanotechnol. 11, 37–41 (2016a).
  * Tran  _et al._ (2016b) Toan Trong Tran, Christopher Elbadawi, Daniel Totonjian, Charlene J. Lobo, Gabriele Grosso, Hyowon Moon, Dirk R. Englund, Michael J. Ford, Igor Aharonovich, and Milos Toth, “Robust multicolor single photon emission from point defects in hexagonal boron nitride,” ACS Nano 10, 7331–7338 (2016b).
  * Vogl  _et al._ (2017) Tobias Vogl, Yuerui Lu, and Ping Koy Lam, “Room temperature single photon source using fiber-integrated hexagonal boron nitride,” J. Phys. D: Appl. Phys. 50, 295101 (2017).
  * Vogl  _et al._ (2018) Tobias Vogl, Geoff Campbell, Ben C. Buchler, Yuerui Lu, and Ping Koy Lam, “Fabrication and deterministic transfer of high-quality quantum emitters in hexagonal boron nitride,” ACS Photonics 5, 2305–2312 (2018).
  * Nikolay  _et al._ (2019) Niko Nikolay, Noah Mendelson, Ersan Özelci, Bernd Sontheimer, Florian Böhm, Günter Kewes, Milos Toth, Igor Aharonovich, and Oliver Benson, “Direct measurement of quantum efficiency of single-photon emitters in hexagonal boron nitride,” Optica 6, 1084–1088 (2019).
  * Vogl  _et al._ (2019c) Tobias Vogl, Marcus W. Doherty, Ben C. Buchler, Yuerui Lu, and Ping Koy Lam, “Atomic localization of quantum emitters in multilayer hexagonal boron nitride,” Nanoscale 11, 14362–14371 (2019c).
  * Mendelson  _et al._ (2020) Noah Mendelson, Dipankar Chugh, Jeffrey R. Reimers, Tin S. Cheng, Andreas Gottscholl, Hu Long, Christopher J. Mellor, Alex Zettl, Vladimir Dyakonov, Peter H. Beton, Sergei V. Novikov, Chennupati Jagadish, Hark Hoe Tan, Michael J. Ford, Milos Toth, Carlo Bradac, and Igor Aharonovich, “Identifying carbon as the source of visible single photon emission from hexagonal boron nitride,” arXiv:2003.00949 (2020).
  * Liu  _et al._ (2020) Wei Liu, Yi-Tao Wang, Zhi-Peng Li, Shang Yu, Zhi-Jin Ke, Yu Meng, Jian-Shun Tang, Chuan-Feng Li, and Guang-Can Guo, “An ultrastable and robust single-photon emitter in hexagonal boron nitride,” Physica E Low Dimens. Syst. Nanostruct. 124, 114251 (2020).
  * Chejanovsky  _et al._ (2016) Nathan Chejanovsky, Mohammad Rezai, Federico Paolucci, Youngwook Kim, Torsten Rendler, Wafa Rouabeh, Felipe Fávaro de Oliveira, Patrick Herlinger, Andrej Denisenko, Sen Yang, Ilja Gerhardt, Amit Finkler, Jurgen H. Smet, and Jörg Wrachtrup, “Structural attributes and photodynamics of visible spectrum quantum emitters in hexagonal boron nitride,” Nano Lett. 16, 7037–7045 (2016).
  * Choi  _et al._ (2016) Sumin Choi, Toan Trong Tran, Christopher Elbadawi, Charlene Lobo, Xuewen Wang, Saulius Juodkazis, Gediminas Seniutinas, Milos Toth, and Igor Aharonovich, “Engineering and localization of quantum emitters in large hexagonal boron nitride layers,” ACS Appl. Mater. Interfaces 8, 29642–29648 (2016).
  * Dietrich  _et al._ (2018) A. Dietrich, M. Bürk, E. S. Steiger, L. Antoniuk, T. T. Tran, M. Nguyen, I. Aharonovich, F. Jelezko, and A. Kubanek, “Observation of Fourier transform limited lines in hexagonal boron nitride,” Phys. Rev. B 98, 081414(R) (2018).
  * Noh  _et al._ (2018) Gichang Noh, Daebok Choi, Jin-Hun Kim, Dong-Gil Im, Yoon-Ho Kim, Hosung Seo, and Jieun Lee, “Stark tuning of single-photon emitters in hexagonal boron nitride,” Nano Lett. 18, 4710–4715 (2018).
  * Mendelson  _et al._ (2019) Noah Mendelson, Zai-Quan Xu, Toan Trong Tran, Mehran Kianinia, John Scott, Carlo Bradac, Igor Aharonovich, and Milos Toth, “Engineering and tuning of quantum emitters in few-layer hexagonal boron nitride,” ACS Nano 13, 3132–3140 (2019).
  * White  _et al._ (2020) Simon J. U. White, Friederike Klauck, Toan Trong Tran, Nora Schmitt, Mehran Kianinia, Andrea Steinfurth, Matthias Heinrich, Milos Toth, Alexander Szameit, Igor Aharonovich, and Alexander Solntsev, “Quantum random number generation using a solid-state single-photon source,” arXiv:2001.10625 (2020).
  * Chen  _et al._ (2020) Yongliang Chen, Thinh Ngoc Tran, Ngoc My Hanh Duong, Chi Li, Milos Toth, Carlo Bradac, Igor Aharonovich, Alexander Solntsev, and Toan Trong Tran, “Optical thermometry with quantum emitters in hexagonal boron nitride,” ACS Appl. Mater. Interfaces 12, 25464–25470 (2020).
  * Sawant  _et al._ (2014) Rahul Sawant, Joseph Samuel, Aninda Sinha, Supurna Sinha, and Urbasi Sinha, “Nonclassical paths in quantum interference experiments,” Phys. Rev. Lett. 113, 120406 (2014).
  * De Raedt  _et al._ (2012) Hans De Raedt, Kristel Michielsen, and Karl Hess, “Analysis of multipath interference in three-slit experiments,” Phys. Rev. A 85, 012101 (2012).
  * Qian  _et al._ (2020) X.-F. Qian, K. Konthasinghe, S. K. Manikandan, D. Spiecker, A. N. Vamivakas, and J. H. Eberly, “Turning off quantum duality,” Phys. Rev. Research 2, 012016 (2020).
  * Gisin  _et al._ (2002) Nicolas Gisin, Grégoire Ribordy, Wolfgang Tittel, and Hugo Zbinden, “Quantum cryptography,” Rev. Mod. Phys. 74, 145–195 (2002).
  * Knopf  _et al._ (2019) Heiko Knopf, Nils Lundt, Tobias Bucher, Sven Höfling, Sefaattin Tongay, Takashi Taniguchi, Kenji Watanabe, Isabelle Staude, Ulrike Schulz, Christian Schneider, and Falk Eilenberger, “Integration of atomically thin layers of transition metal dichalcogenides into high-Q, monolithic Bragg-cavities: an experimental platform for the enhancement of the optical interaction in 2D-materials,” Opt. Mater. Express 9, 598–610 (2019).
  * Żukowski  _et al._ (1997) Marek Żukowski, Anton Zeilinger, and Michael A. Horne, “Realizable higher-dimensional two-particle entanglements via multiport beam splitters,” Phys. Rev. A 55, 2564–2579 (1997).


# Lossless Point Cloud Attribute Compression with Normal-based Intra
Prediction
††thanks: *Jianwen Chen is the corresponding author. © 2021 IEEE. Personal use
of this material is permitted. Permission from IEEE must be obtained for all
other uses, in any current or future media, including reprinting/republishing
this material for advertising or promotional purposes, creating new collective
works, for resale or redistribution to servers or lists, or reuse of any
copyrighted component of this work in other works.

Qian Yin, Qingshan Ren, Lili Zhao, Wenyi Wang, and Jianwen Chen  School of
Information and Communication Engineering
University of Electronic Science and Technology of China
Chengdu, China
<EMAIL_ADDRESS>
###### Abstract

The sparse LiDAR point clouds become more and more popular in various
applications, e.g., the autonomous driving. However, for this type of data,
there exists much under-explored space in the corresponding compression
framework proposed by MPEG, i.e., geometry-based point cloud compression
(G-PCC). In G-PCC, only the distance-based similarity is considered in the
intra prediction for the attribute compression. In this paper, we propose a
normal-based intra prediction scheme, which provides a more efficient lossless
attribute compression by introducing the normals of point clouds. The angle
between normals is used to further explore accurate local similarity, which
optimizes the selection of predictors. We implement our method into the G-PCC
reference software. Experimental results over LiDAR acquired datasets
demonstrate that our proposed method is able to deliver better compression
performance than the G-PCC anchor, with $2.1\%$ gains on average for lossless
attribute coding.

###### Index Terms:

3D point cloud, G-PCC, attribute compression, normal-based prediction

##  I Introduction

With rapid development of 3D sensing and capturing technologies, point clouds,
which have the capacity of representing spatial structures and surface
properties of 3D objects or scenes, are often encountered in various fields,
e.g., the autonomous driving, the heritage reconstruction and 3D immersive
communication [1]. However, it is well-known that point clouds have the
unorganized distribution in 3D space and consist of millions of points, which
imposes the burden on the limited transmission bandwidth and storage space.
Therefore, the compression of point clouds is indispensable but challenging.
Therefore, it is necessary to explore more effective point cloud compression
(PCC) schemes.

(a)

(b)

(c)

Figure 1: Three single frame snapshots with bird views from Ford sequences
provided by MPEG, which are point clouds acquired by LiDAR sensors. (a)
Ford_02_vox1mm-0100. (b) Ford_01_vox1mm-0100. (c) Ford_03_vox1mm-0200.

Due to the potential needs of point cloud related applications, the Moving
Picture Experts Group (MPEG) establishes the MPEG-3DG subgroup to exploit
universal PCC frameworks. Two standardized test models are proposed: the
video-based PCC (V-PCC) [2] and the geometry-based PCC (G-PCC) [3]. For V-PCC,
3D point clouds are projected into the 2D domain, and then coded by using the
existing video codec (e.g., High Efficiency Video Coding, HEVC [4]), which is
more suitable for the dense point cloud compression. The G-PCC, by contrast,
performs better for the sparse point cloud by compressing point clouds in the
original 3D space. It is noted that point clouds typically consist of geometry
information (i.e., 3D coordinates) and attribute information (e.g., colors,
reflectances and normals). In the existing PCC schemes, the geometry and
attribute information are coded separately. In this work, we focus on the
attribute lossless coding in G-PCC for point clouds acquired by LiDAR sensors.
Some examples can be seen in Fig. $1$.

Among the existing methods for the point cloud attribute coding, one popular
strategy is the _Graph Fourier Transform_ (GFT) (e.g., [5], [6], [7]). In [5],
Zhang et al. proposed an attribute compression method based on the graph
transform. This scheme delivers a more effective PCC by using GFT instead of
the traditional DCT, but generates many isolated sub-graphs when it comes to
the sparse point clouds. To address this issue, Robert et al. used the
k-nearest neighbours (KNNs) method in [6] and Shao et al. introduced Laplacian
sparsity in [7] to optimize the graph transform respectively. However, due to
much higher computational complexity introduced by eigenvalue decompositions,
it is difficult for these graph-based methods to achieve real-time PCC.

Figure 2: The overview of the attribute encoder in G-PCC.

Besides the GFT-based methods, Queiroz et al. proposed a _region-adaptive
hierarchical transform_ (RAHT) scheme by using the Haar wavelet, which is
combined with a Laplacian distributed entropy coder for the attribute
compression [8]. This method is also adopted in G-PCC to compress the static
point clouds because of its lower complexity. In addition to RAHT, there are
another two schemes also for attribute coding, i.e., the _Lifting Transform_
method [9] and the _Predicting Transform_ [3] method, which aim for lossy
coding and lossless coding respectively. In G-PCC, the Predicting Transform
scheme is a distance-based prediction method by using the k-nearest neighbours
(KNNs) algorithm. However, this scheme, where the attribute similarity is
measured only by the distances between points, fails to fully exploit the
geometrical correlation among neighbors.

It is noted that the angle between normals of points can represent the local
similarity for LiDAR point clouds. Motivated by this, the optimal mode of the
predictor could be more accurately estimated by adding a new descriptor (i.e.,
normals). In this paper, we propose a normal-based intra prediction scheme for
lossless point cloud attribute compression. Based on the original distance-
based prediction method, the normals of point clouds are introduced
additionally to further optimize predictors, which leads to better prediction
mode selections. Extensive experiments are conducted and compared with the
original G-PCC, and the experimental results demonstrate that our method
provides better R-D performance than the G-PCC anchor for the LiDAR point
cloud.

The rest of this paper is organized as follows. Section $2$ describes the
lossless attribute compression method in original MEPG’s G-PCC and Section $3$
presents our proposed normal-based intra prediction scheme. Section $4$
provides experimental results and discussions. Finally, Section $5$ concludes
this paper.

TABLE I: The transform methods for Category $1$ and $3$ under different test
conditions in G-PCC.

Dataset | Test condition for attribute
---|---
Lossy | Near-lossless / Lossless
Category 1 |  RAHT 1 |  Predicting Transform 2
Category 3 |  Lifting Transform 3 |  Predicting Transform 2

  * $1$

region-adaptive hierarchical transform.

  * $2$

interpolation-based hierarchical nearest-neighbour prediction.

  * $3$

interpolation-based hierarchical nearest-neighbour prediction with an
update/lifting step.

##  II The overview of the attribute encoder in MPEG’s G-PCC

Fig. $2$ shows the framework of the attribute encoder in G-PCC, which mainly
consists of the following stages: transferring attributes (the recoloring of
reconstructed point clouds), transformation, quantization and entropy coding.
In this paper, we work on the transformation stage.

From Fig. $2$, it can be observed that at the transformation stage, there
exists a switch between multiple attribute transform strategies, which depends
on various datasets and coding conditions. Specifically, there are two types
of datasets provided by MPEG, i.e., the static point clouds (denoted as
Category $1$) and the dynamically acquired point clouds (denoted as Category
$3$) [10]. As shown in Table $1$, for the lossy coding, the _RAHT_ and
_Lifting Transform_ methods are typically conducted on Category $1$ and
Category $3$ respectively. For the near-lossless and lossless coding, the
_Predicting Transform_ method is used both for Category $1$ and Category $3$.

Figure 3: The flow diagram of the enhanced Predicting Transform framework.
This scheme consists of two parts: one part is the original Predicting
Transform method in G-PCC shown by the dashed box(left), and the other part is
our proposed normal-based prediction scheme shown by the dashed box(right).
The normal-based prediction consists of three stages, which are the normal-
based predictor generation, the predictor enhancement with an angle selection
and the predictor modes decision.

As previously mentioned, we focus on the attribute lossless coding in G-PCC
[3], where the _Predicting Transform_ method is adopted. This method is an
interpolation-based prediction scheme, which is improved by a neighbour weight
modification proposed in [11] for the LiDAR point clouds. Then, an adaptive
predictor selection method [12] is applied to G-PCC and the rate-distortion
optimization (RDO) procedure is used to optimize the prediction scheme, which
is modified according to the attribute range of neighbors for LiDAR point
clouds, as presented in [13].

##  III The proposed method

The proposed prediction framework for the lossless attribute compression, as
shown in Fig. $3$, consists of the level of detail (LOD) generation and the
enhanced Predicting Transform scheme. The LOD structure divides the whole
point cloud into a set of refinement levels. Then, the re-organized point
cloud is processed by the enhanced Predicting Transform scheme, which
incorporates the original Predicting Transform scheme in G-PCC shown by the
dashed box (left) and our proposed normal-based prediction scheme shown by the
dashed box (right). The Section $3.1.$ introduces the normals’ calculation and
integration process. The Section $3.2.$ details our proposed normal-based
prediction scheme, which introduces the generation, enhancement and selection
of the normal-based predictor.

###  III-A The Integration of the Original Distanced-based Prediction and the
Proposed Normal-based Prediction

In G-PCC, the point cloud is first sorted according to their associated Morton
codes in an ascending order, and then divided by the LOD generation process.
In our proposed scheme, we preprocess the re-ordered point clouds by
calculating the normals before the LOD process, which is prepared for the
subsequent normal-based prediction. To be specific, for each point $P_{i}$, we
use the k-d tree to find $N$ nearest neighbors (i.e., $N=15$), which defines
the local plane of $P_{i}$. Then, the normal of the local plane is calculated
by using the eigenvalue decomposition, which serves as the approximate normal
of the point $P_{i}$. The point clouds along with calculated normals are next
re-organized by the LOD structure process.

Fig. $3$ presents the enhanced Predicting Transform framework, where the
original Predicting Transform scheme is as a part shown by the dashed box
(left). It is known that there are mainly three stages in the Predicting
Transform scheme: the distance-based predictor generation, the calculation of
the attribute value range and the selection of predictor modes. At the stage
of the distance-based predictor generation, the distances from the current
point $P_{i}$ to previously encoded points are computed and then $k$ ($k=3$)
nearest neighbour points of $P_{i}$ can be selected.

Based on 3 selected points, the distance-based predictor is generated, which
is then utilized for the selection of predictor modes. Specifically, the
differences between each pair of three nearest neighbors are computed in turn,
and then the maximum difference can be available, denoted as _max_diff_. By
comparing the _max_diff_ with a pre-defined threshold, different predictor
modes are selected accordingly. In G-PCC, there are four predictor modes,
denoted as Mode $0$, Mode $1$, Mode $2$ and Mode $3$ respectively. Mode $0$
represents an interpolation-based prediction with the Inverse Distance
Weighted (IDW) method by using $3$ nearest-neighbors. For Mode $1$, Mode $2$
and Mode $3$, $1^{st}$, $2^{nd}$ and $3^{rd}$ nearest neighbors are directly
used to predict the current point respectively.

From Fig. $3$, it can be observed that when the _max_diff_ of the neighbor’s
reflectance exceeds the pre-defined threshold, the current point $P_{i}$ is
adaptively predicted from three predictor candidates (Mode $1$, Mode $2$ and
Mode $3$) by using the rate-distortion optimization (RDO) procedure.
Otherwise, Mode $0$ will be chosen. In this case, instead of using Mode $0$,
our proposed normal-based predictor is applied, which aims to optimize the
selection of predictor candidates. The specific procedure is shown in Fig. $3$
denoted with the dashed box (right). The main novelty is that, in addition to
the predictor in the original G-PCC using the similarity in distances between
coordinates, our proposed method further explores the local similarity among
points by introducing the angle between normals.

TABLE II: The comparison results between our method and the G-PCC anchor on Category 3-frame under the condition CW. Sequences | Frame | Input Points | Geometry | Peak | $\Delta R$ (%)
---|---|---|---|---|---
Number | Precision (bits) | Value
ford_01_q1mm | 1500 | 123940658 | 18 | 30000 | -1.3
ford_02_q1mm | 1500 | 125751705 | 18 | 30000 | -1.0
ford_03_q1mm | 1500 | 126093865 | 18 | 30000 | -0.9
qnxadas-junction-approach | 74 | 2233793 | 18 | 30000 | -2.8
qnxadas-junction-exit | 74 | 2016190 | 18 | 30000 | -5.6
qnxadas-motorway-join | 500 | 14430189 | 18 | 30000 | -4.5
qnxadas-navigating-bends | 300 | 8167066 | 18 | 30000 | -4.0
Cat3-frame average |  |  |  |  | -2.1

###  III-B The Generation, Enhancement and Selection of the Normal-based
Predictor

The normal-based prediction method is shown in Fig. $3$ with the dashed box
(right), which mainly consists of three stages: the normal-based predictor
generation, the predictor enhancement with an angle selection and the
predictor modes decision. To be specific, the normal-based predictor is
generated on top of the previous distance-based predictor, by introducing the
normals of $3$ nearest-neighbors.

The normal-based predictor obtained above is then improved by an angle
selection. The calculation of the angle between normals is shown in Fig. $4$.
Let $V_{i}$ and $V_{j}$ be the normals of the points $P_{i}$ and $P_{j}$
respectively. Then, the angle $\theta$ between normals $V_{i}$ and $V_{j}$ is
calculated by

$\displaystyle\theta$ $\displaystyle=$
$\displaystyle\arccos\left(\frac{V_{i}\cdot
V_{j}}{\left\|V_{i}\right\|\cdot\left\|V_{j}\right\|}\right).$ (1)

At the stage of the predictor enhancement, considering the similarity of the
attributes decreases with the increase of the distance between point clouds,
we only use the $1^{st}$ nearest neighbouring point, which is to enhance the
normal-based predictor with an angle selection. Specifically, we calculate the
angle between normals of $1^{st}$ nearest neighbor and the current point based
on Equation (1), denoted as the $normal\\_angle$.

From Fig. $3$, it can be observed that when the $normal\\_angle$ is greater
than $90^{\circ}$, Mode $0$ is selected by using the weighted average of
neighbors’ attributes for the prediction. If not, Mode $1$ is selected by
using the $1^{st}$ neighbor to predict the current point. Note that Mode $0$
and Mode $1$ follow the same paradigm adopted in G-PCC.

Figure 4: The schematic diagram of calculation for the angle between normals.
$V_{i}$ and $V_{j}$ are normals of point $P_{i}$ and $P_{j}$ respectively. The
angle between normals of points is denoted as $\theta$.

Finally, the prediction residuals are processed by the quantizer and
arithmetic encoder. It is worth to mention that no extra flags or parameters
are required to be written into the final bitstream, because the decoder is
implemented by repeating the operation of the normal-based prediction scheme.

##  IV experimental results

To evaluate the effectiveness of our proposed normal-based intra prediction
scheme, extensive simulations have been conducted on the test dataset provided
by MPEG. We incorporate our method into the MPEG G-PCC reference software,
i.e., TMC13v10 [3], and compare its compression performance [14] of attribute
compression with the original TMC13.

In our experiments, the test dataset consists of seven dynamically acquired
point clouds (denoted as Category $3$-frame). Among them, three ford
sequences, _ford_01_q1mm_ , _ford_02_q1mm_ , and _ford_03_q1mm_ can be
available by [15], while the other four qnxadas sequences, _qnxadas-junction-
approach_ , _qnxadas-junction-exit_ , _qnxadas-motorway-join_ , and _qnxadas-
navigating-bends_ , can be obtained in [16]. More details of the
Category$3$-frame dataset are listed in Table II. All the experiments are
conducted under CW condition of the Common Test Conditions (CTC) [10], where
CW represents lossless geometry and lossless attribute.

Table II shows the comparison results between proposed method and the G-PCC
anchor on the Category $3$-frame under the CW condition. Since this work aims
for lossless compression with no distortion of data, the commonly-used
evaluation metric, measuring the rate in terms of bits for attributes, bits
per input point (denoted as $bpip$), is used for evaluation. Specifically, we
compute the $bpip$ of the proposed method and that of the TMC13, and then the
bit saving ratio ($\Delta R$) can be obtained for the final performance
evaluation, which is defined as

$\Delta R=\frac{bpip_{ours}-bpip_{tmc13}}{bpip_{tmc13}}\times 100\%$ (2)

From equation (2), we can see that the proposed method outperforms the anchor
(TMC13) when the bit saving rate $\Delta R$ is negative. Otherwise, it means
that the anchor shows better performance than the proposed method.

From Table II, it can be obviously observed that the bit savings can be
achieved with 2.1% on average, especially for sequence _qnxadas-junction-exit_
, up to 5.6%. From the results, we can see that our proposed method is
effective on the LiDAR datasets for attribute lossless compression in G-PCC.
The rationale behind the gains is that by introducing our normal-based
prediction scheme, the attribute similarity can be explored more accurately,
which leads to better selection of the predictor mode.

##  V conclusion

In this paper, to improve the efficiency of the lossless attribute compression
in G-PCC, a normal-based intra prediction scheme is proposed, which further
exploits the geometrical correlations among neighbors in point clouds. Based
on the original distance-based Predicting Transform scheme, the normals of
each point, as an additional descriptor, are introduced to optimize original
predictors. By computing the angle between normals, a better predictor mode
can be selected. Experimental results have demonstrated that our method is
able to consistently deliver a better performance than the G-PCC test model.

## References

  * [1] C. Tulvan, R. Mekuria, and Z. Li,  “Use cases for point cloud compression(PCC), document N16331,”  ISO/IEC JTC 1/SC 29/WE 11 MPEG, Geneva, Jun. 2016.
  * [2] “V-PCC codec description, document N19332,”  ISO/IEC JTC 1/SC 29/WE 11 MPEG, Alpbach, Apr. 2020.
  * [3] “G-PCC codec description, document N19331,”  ISO/IEC JTC 1/SC 29/WE 11 MPEG, Alpbach, Apr. 2020.
  * [4] G. J. Sullivan, J. Ohm, W. Han, and T. Wiegand,  “Overview of the high efficiency video coding (HEVC) standard,”  IEEE Trans. Circuits Syst. Video Techn., vol. 22, no. 12, pp. 1649–1668, Sep. 2012.
  * [5] C. Zhang, D. Florêncio, and C. Loops,  “Point cloud attribute compression with graph transform,”  in Proc. IEEE Int. Conf. Image Process. (ICIP), Sep. 2014, pp. 2066–2070.
  * [6] R. A. Cohen, D. Tian, and A. Vetro,  “Attribute compression for sparse point clouds using graph transforms,”  in Proc. IEEE Int. Conf. Image Process. (ICIP), Sep. 2016, pp. 1374–1378.
  * [7] Y. Shao, Z. Zhang, Z. Li, K. Fan, and G. Li,  “Attribute compression of 3D point clouds using laplacian sparsity optimized graph transform,”  in Proc. IEEE Int. Conf. Visual Commun. Image Process. (VCIP), Dec. 2017, pp. 10–13.
  * [8] R. L. de Queiroz and P. A. Chou,  “Compression of 3D point clouds using a region-adaptive hierarchical transform,”  IEEE Trans. Image Process., vol. 25, no. 8, pp. 3947–3956, Aug. 2016.
  * [9] “Lifting scheme for lossy attribute encoding in TMC1, document m42640,”  ISO/IEC JTC 1/SC 29/WE 11 MPEG, San Diego, Apr. 2018.
  * [10] “Common test conditions for point cloud compression, document N19324,”  ISO/IEC JTC 1/SC 29/WE 11 MPEG, Alpbach, Apr. 2020.
  * [11] “CE13.20 report on neighbor’s weight modification on Lifting and Predicting Scheme, document m50773,”  ISO/IEC JTC 1/SC 29/WE 11 MPEG, Geneva, Oct. 2019.
  * [12] “PCC Adaptive predictor selection for attributes coding in TMC13 related to CE13.3, document m43665,”  ISO/IEC JTC 1/SC 29/WE 11 MPEG, Ljubljana, Jul. 2018.
  * [13] “[G-PCC][New Proposal] on improvement for adaptive reflectance predictor selection, document m50765,”  ISO/IEC JTC 1/SC 29/WE 11 MPEG, Geneva, Oct. 2019.
  * [14] “G-PCC performance evaluation and anchor results, document N19326,”  ISO/IEC JTC 1/SC 29/WE 11 MPEG, Alpbach, Apr. 2020.
  * [15] G. Pandey, James R. Mcbride, and Ryan M. Eustice,  “Ford Campus vision and lidar data set,”  The International Journal of Robotics Research, vol. 30, no. 13, pp. 1543–1552, 2011.
  * [16] “PCC Cat3 test sequences from BlackBerry—QNX, document m23647,”  ISO/IEC JTC 1/SC 29/WE 11 MPEG, Ljubljana, July. 2018.