also at ]PSR, Brazil

# Two-photon quantum state tomography of photonic qubits

Guilherme P. Temporão<EMAIL_ADDRESS>Pedro Ripper
<EMAIL_ADDRESS>[  Department of Electrical Engineering,
Pontifical Catholic University of Rio de Janeiro, Brazil  Thiago B. Guerreiro
<EMAIL_ADDRESS>Department of Physics, Pontifical Catholic University of
Rio de Janeiro, Brazil  Gustavo C. do Amaral<EMAIL_ADDRESS>Quantum Technology Department, The Netherlands Organization for Applied
Scientific Research, TNO, The Netherlands

###### Abstract

We provide a tool for measuring the Stokes parameters and the degree of
polarization of single photons by employing second order interference, namely
the Hong-Ou-Mandel (HOM) interferometer. It is shown that the technique is
able to distinguish a partially polarized photon where the polarization state
is coupled to an internal degree of freedom, such as time of arrival, from
partial polarization due to external entanglement with the environment. The
method does not directly resort to any kind of polarization-selective
components and therefore is not limited by the extinction ratio of polarizers.
Moreover, the technique can be generalized to any two-level encoding of
quantum information in single photons, such as time-bin or orbital angular
momentum qubits.

††preprint: APS/123-QED

##  I Introduction

The need for single-photon sources (SPS) is increasing for many applications,
such as quantum communication, photonic quantum computing and quantum
metrology [1, 2, 3]. Therefore, tools for characterization of such sources are
of paramount importance. One of the most important aspects of a SPS is the
polarization purity of the generated photons, usually called degree of
polarization (DOP), which can be measured by standard polarimetry, i.e.,
polarization Quantum State Tomography (QST) [4, 5, 6, 7]. In standard QST, the
polarization state of the photons is determined by a succession of
measurements of Pauli operators, which are measurements acting on individual
photons, one at a time. However, polarization measurements employing two-
photon interference, namely the Hong-Ou-Mandel (HOM) effect [8], have recently
been employed for tracking changes in the polarization state over time, with
many advantages over the standard methods [9, 10, 11].

In this work, we use the HOM effect for performing full quantum state
tomography on the polarization state of the photons, thus obtaining
information on the Stokes parameters and the photons DOP by second-order
interference. The additional benefit of this method is that we can access
additional degress of freedom of the photons with a significantly smaller
number of measurements if compared to classical measurements, which can be
regarded as a kind of quantum advantage [12]. As will be shown in calculations
and simulations in quantum circuits, the proposed method can detect
decoherence effects due to the coupling of the polarization state of the
photon to other internal degrees of freedom, such as time of arrival, spatial
mode or frequency mode, and therefore distinguishing them from external
couplings to the environment or statistical mixtures. The method has
applications beyond polarimetry, as it can be generalized to characterize any
qubit encoding in a single photon. Towards that end, we compare the proposed
method against standard QST on a quantum computer simulator to demonstrate its
expected performance and encoding generality.

##  II Method

Fig. 1 shows the basic idea of the method, which consists of interfering two
single photons on a beamsplitter (BS). Here, the source producing the two
input single-photon states are not necessarily the same, the only requirement
being that the quantum state originally encoded onto the two photons (denoted
$\ket{\psi}$ in Fig. 1) is the same; furthermore, before reaching the
beamsplitter, one of the two input states is subjected to a polarization
transformation represented by the unitary operation $U$. Let $\mathcal{H}$ be
the Hilbert space describing all degrees of freedom of the photons, and write
$\mathcal{H}=\mathcal{H}_{\text{pol}}\otimes\mathcal{H}_{\text{o}}$, where
$\mathcal{H}_{\text{pol}}$ is the (two-dimensional) Hilbert space associated
with the polarization state of the photons and $\mathcal{H}_{\text{o}}$ is the
Hilbert space associated with the remaining degrees of freedom. Whenever the
incoming states are pure (i.e., there is no entanglement between the photons
and any external degree of freedom), we can write a generic input state as:

$\ket{\psi}=\sqrt{p}\ket{\phi}\ket{\xi}+e^{i\theta}\sqrt{1-p}\ket{\phi^{\perp}}\ket{\xi^{\perp}}$
(1)

where $\ket{\phi}\in\mathcal{H}_{\text{pol}}$,
$\ket{\xi}\in\mathcal{H}_{\text{o}}$, $\theta$ is a generic phase, the sign
$\perp$ means a orthogonal state and $p$ is a real parameter $(0\leq p\leq 1)$
that can be interpreted as a probability of finding the photon in the
polarization state $\ket{\phi}$. Note that Eq. 1 describes a partially
polarized photon whenever $0<p<1$.

Figure 1: Scheme for determining the polarization state of single photons. Two
identical photons represented by the quantum state $\ket{\psi}$, where one of
them is subjected to a unitary operator $U$, interfere in a beamsplitter (BS)
and the probability of coincidence counts in the single-photon detectors (SPD)
is determined, according to Eq. 2. If $U$ is replaced successively by the
Pauli operators $\sigma_{j}$, the coincidence probabilities
$P_{coinc}(\sigma_{j})$ can be used to calculate the DOP and the absolute
value of the Stokes parameters of the original photons. Additional steps may
be added for obtaining full information on the quantum state, as described in
Appendix A.

Using two threshold single-photon detectors (SPD) in the BS outputs, the
probability of obtaining a coincidence count $P_{coinc}$ as a function of the
applied unitary operator $U$ is given by the following expression:

$P_{coinc}(U)=\frac{1-\mathcal{F}(U)}{2}$ (2)

where $\mathcal{F}(U)$ is the fidelity between the two input quantum states
impinging on the BS when an unitary operator
$U\in\mathcal{B}[\mathcal{H}_{\text{pol}}]$ is applied to one of the inputs.
The derivation of Eq. 2 can be found in Appendix B. Note that, due to the
single-photon nature of the input states, the HOM visibility reaches 100% when
the photons are indistinguishable; this, however, does not limit the
effectiveness of the method when different photon statistics are considered,
but it does impact its performance [13]. The fidelity is given by:

$\mathcal{F}(U)=|\braket{\psi}{U\otimes I}{\psi}|^{2}$ (3)

where $I$ is the identity operator acting on $\mathcal{H}_{\text{o}}$.

Now recall from standard polarimetry that the (normalized) Stokes parameters
are defined, for pure polarization states, as:

$s_{j}\equiv\text{tr}\left(\ket{\psi}\bra{\psi}\sigma_{j}\right)=\braket{\phi}{\sigma_{j}}{\phi}$
(4)

i.e., they correspond to the expectation values of the Pauli spin operators.
Under the context of polarization states, they can be written as:

$\displaystyle\sigma_{1}\equiv$ $\displaystyle\ket{H}\bra{H}-\ket{V}\bra{V}$
$\displaystyle\sigma_{2}\equiv$
$\displaystyle\ket{+45}\bra{+45}-\ket{-45}\bra{-45}$
$\displaystyle\sigma_{3}\equiv$
$\displaystyle\ket{RC}\bra{RC}-\ket{LC}\bra{LC}$ (5)

where $\\{\ket{H},\ket{V}\\}$ are the horizontal and vertical polarizations,
$\\{\ket{+45},\ket{-45}\\}$ are the diagonal/anti-diagonal polarizations and
$\\{\ket{RC},\ket{LC}\\}$ correspond to the right-circular/left-circular pure
polarization states. The reader should be aware of the unusual labeling of the
Pauli operators; this is due to the re-labeling of the axes when going from
the Bloch sphere to Poincaré sphere.

Let us now consider a simplified version of the protocol, where we are only
interested in finding the DOP of the photons; we also assume for the moment
that there is no external entanglement taking place - see section III.2 for a
discussion and Appendix A for the full protocol. The idea consists in
sequentially selecting $U=\sigma_{j}$, for $j=1,2,3$. It is straightforward
from Eq. 3 and Eq. 1 that

$\displaystyle\mathcal{F}(\sigma_{j})$
$\displaystyle=|p\braket{\phi}{\sigma_{j}}{\phi}+(1-p)\braket{\phi^{\perp}}{\sigma_{j}}{\phi^{\perp}}|^{2}$
(6) $\displaystyle=[(2p-1)s_{j}]^{2}$ $\displaystyle=\langle s_{j}\rangle^{2}$

where $\langle s_{j}\rangle$ are defined as the time averaged Stokes
parameters. The probabilities of coincidence as a function of the applied
Pauli operator can be found by replacing Eq. 6 on 2:

$P_{coinc}(\sigma_{j})=\frac{1-\langle s_{j}\rangle^{2}}{2}$ (7)

The degree of polarization (DOP), on the other hand, corresponds to the norm
of the Stokes vector. Using the usual definition for DOP, we have:

$DOP=\left[\sum_{j=1}^{3}\langle s_{j}\rangle^{2}\right]^{1/2}$ (8)

Equation 8 is somewhat surprising, as the degree of polarization of light can
be determined without any polarization-selective component, such as polarizers
or polarizing beamsplitters (PBS). It is straightforward to show that the
state $\ket{\psi}$ given by Eq. 1 has $DOP=|2p-1|$.

It should be stressed that the presented method so far is able to determine
the absolute values of the Stokes parameters, $|s_{j}|$, but not their signs.
Additional measurements, and the inclusion of a polarization dependent loss
(PDL) element in front of one of the detectors, is a possible way to
circumvent this limitation; the full protocol for complete characterization of
the polarization state is described in Appendix A.

##  III Application of the method in partially polarized light

Partially polarized light may be obtained in two ways. The first one is by
incoherently mixing polarized photons, whereas the second one consists of, for
each photon, entangling the polarization state with another degree of freedom
of a different nature, thus obtaining a partially polarized photon. In the
next sections, we discuss the cases of “internal” and “external” entanglement
in partially polarized photons, which correspond, respectively, to internal
degrees of freedom of the photon and external quantum systems, commonly
referred to as the environment. The case of incoherent mixtures, as will be
discussed, is indistinguishable from external entanglement.

###  III.1 “Internal” entanglement

We provide now an example where the polarization degree of freedom is
entangled with the photon time-of-arrival, usually called “time-bin” in the
context of quantum communications [14], in order to show that the definition
in Eq. 8 coincides with the usual DOP definition for such states. Let
$\\{\ket{t_{0}},\ket{t_{1}}\\}$ represent the states where the photon wave-
packets are centered at times of arrival $t_{0}$ and $t_{1}=t_{0}+\Delta t$,
where the delay $\Delta t$ between each bin is longer than the photon
coherence time $\tau_{c}$.

Figure 2: Partially polarized light due to polarization-time coupling, where
$\alpha,\beta$ are complex numbers such that $|\alpha|^{2}+|\beta|^{2}=1$. The
standard definition of degree of polarization yields $DOP=|2|\alpha|^{2}-1|$,
which is shown to coincide with the proposed method.

From the point of view of the polarization state alone, the state depicted in
Fig. 2 corresponds to partially polarized light. The polarization state of
$\ket{\psi}$ is given by the reduced density operator obtained by tracing over
the Hilbert space $\mathcal{H}_{\text{o}}$:

$\rho=\text{tr}_{\mathcal{H}_{o}}\ket{\psi}\bra{\psi}=\begin{pmatrix}|\alpha|^{2}&0\\\
0&1-|\alpha|^{2}\\\ \end{pmatrix}$ (9)

As expected, the off-diagonal components of $\rho$ are zero, such that
$s_{2}=s_{3}=0$, and the degree of polarization is simply given by

$DOP=|s_{1}|=\text{tr}(\rho\sigma_{1})=|2|\alpha|^{2}-1|$ (10)

Now, consider the two-photon interference measurement of the state depicted in
Fig. 2. It is straightforward to show that this is a particular case of Eq. 1
with $\xi=t_{0}$ and $\xi^{\perp}=t_{1}$, such that Eq. 6 now yields:

$\mathcal{F}(U)=\left||\alpha|^{2}\braket{H}{U}{H}+|\beta|^{2}\braket{V}{U}{V}\right|^{2}$
(11)

which is clearly zero for $U\in\\{\sigma_{2},\sigma_{3}\\}$ and equal to
$|\alpha|^{2}-|\beta|^{2}=|2|\alpha|^{2}-1|$ for $U=\sigma_{1}$, which
coincides with the standard tomography result given by Eq. 10. For a detailed
calculation we refer the reader to Appendix B.

As previously mentioned, when $U=I$, we have $\mathcal{F}(I)=1$, which
translates to a zero coincidence probability in the HOM setting, according to
Eq. 2. This result, in fact, occurs independently of the way the polarization
state is coupled to any inner degree of freedom of the photon, since the two
input states of the BS are identical and will result in photon bunching. This
is a remarkable advantage of the proposed protocol: by measuring the
coincidence probability $P_{coinc}(I)$, one can verify whether the incoming
state is indeed a pure state.

###  III.2 “External” entanglement and incoherent mixtures of pure states

If the coincidence probability $P_{coinc}(I)>0$, the input states are not pure
states; by ”pure” state, we mean the density matrix that encompasses all
degrees of freedom of the single photon can be represented by a rank 1
projector. If the coincidence rate is greater than zero, then two
possibilities arise: first, the case where random time-varying unitary
operations produce resulting mixed states, i.e, incoherent mixtures of pure
states; second, and assuming that the two photons at the BS inputs have been
collected from the SPS in a controllable way – such that we can rule out such
fast unitary operations –, the case where the polarization state and an
external degree of freedom are entangled. Examples of the latter are two
photons that are each half of a polarization-entangled pair; or photons
produced through the decay of an atomic level that retains information about
the polarization state of the photon, as in certain Raman-based atom-photon
entanglement protocols [15]. In both cases described above, the input states
in Fig. 1 are now represented by a density operator $\rho$. Irrespective of
the actual nature of $\rho$, we can always write:

$\rho=\lambda\ket{\phi}\bra{\phi}+(1-\lambda)\ket{\phi^{\perp}}\bra{\phi^{\perp}}$
(12)

where the parameter $\lambda$ is directly related to the DOP = $|2\lambda-1|$.
Now we can apply the following reasoning: whenever both inputs are identical,
which occurs with probability $\lambda^{2}+(1-\lambda)^{2}$, the fidelity is
one; however, when both inputs are different, which happens with probability
$2\lambda(1-\lambda)$, the fidelity is zero. Therefore, the average fidelity
is given by $\mathcal{F}(I)=\lambda^{2}+(1-\lambda)^{2}$, which corresponds to
a coincidence probability given by:

$P_{coinc}(I)=\lambda(1-\lambda).$ (13)

For the Stokes parameters $\\{s_{j}\\}$, the calculation is somewhat different
from the case of pure states, given by Eq. 6. Indeed, Eq. 6 considers that all
degrees of freedom are available when performing the inner product in Eq. 3.
Here, the fidelity is taken over two mixed states, i.e., between $\rho$ and
$U\rho U^{\dagger}$. A simple calculation shows that:

$\mathcal{F}(\sigma_{j})=s_{j}^{2}[\lambda^{2}+(1-\lambda)^{2}]+(1-s_{j}^{2})2\lambda(1-\lambda)$
(14)

Note that whenever $\lambda=0$ or $\lambda=1$, Eq. 14 reduces to Eq. 6, as
expected. The probabilities of coincidence for a generalized state now read:

$P_{coinc}(\sigma_{j})=\frac{1-\langle s_{j}\rangle^{2}}{2}-P_{coinc}(I),$
(15)

where $\langle s_{j}\rangle=s_{j}|2\lambda-1|$, a generalization of Eq. 7.

It is interesting to identify that $\lambda$ now has a two-fold effect on
$P_{coinc}(\sigma_{j})$: it acts on the first right hand side term of Eq. 15
similarly to $p$ in Eq. 6, but the existence of external entanglement
decreases all coincidence probabilities by $P_{coinc}(I)$, also governed by
$\lambda$. Whenever $\lambda=\tfrac{1}{2}$, the probabilities are all equal to
$\tfrac{1}{4}$, as one should expect: two completely mixed states impinging on
the beamsplitter correspond to a 50-50 mixture of two identical states (zero
coincidence probability) and two orthogonal states (50% coincidence
probability). Again, external entanglement is indistinguishable from
incoherent mixtures of pure states; however, as long as random time-varying
unitary operations are known to be not present, this protocol allows one to
distinguish between “inner” and “outer” entanglement scenarios by computing
$P_{coinc}(I)$ and verifying whether it is equal to zero (“inner”
entanglement) or grater than zero (“outer” entanglement). Conversely, when
entanglement with external degrees of freedom can be neglected or prevented,
the protocol is able to distinguish between internal entanglement and
incoherent mixtures. In both cases, these distinctions are unattainable in
standard quantum state tomography.

Finally, it should be mentioned that both kinds of entanglement can be
quantified, e.g., by calculating the von Neumann entropy of the reduced
density matrix, $S(\rho)$, as usual.

###  III.3 Advantages over Standard QST

The main advantage of the method stems from the combination of the calculated
DOP from Eq. 8 and the coincidence probability $P_{coinc}(I)$. If $\rho$ is
the density operator representing all (internal) degrees of freedom of the
photon, then by definition $P_{coinc}(I)=\text{tr}(\rho^{2})$. This
information, together with the DOP value, answers the following two questions
at the same time: (i) “Is there entanglement between the polarization state
and another internal degree of freedom?” and (ii) “Is there entanglement
between a internal degree of freedom of the photon and an external environment
or, alternatively, an incoherent mixture prepared using classical probability
sampling?”

Standard QST cannot directly provide these answers, unless all degrees of
freedom are separately discriminated. Let us consider a simpler case where
there are only two degrees of freedom of interest, as in subsection III.1.
Standard QST would need to reconstruct the 4x4 polarization-time-bin density
matrix, which requires measurements of average values of all combinations of
Pauli operators $\sigma_{i}\otimes\sigma_{j}$, which adds up to 16 measurement
rounds; moreover, the detectors would have to be fast enough (and have low
enough jitter) to be able to distinguish arrival times $t_{0}$ from $t_{1}$.
The current method, however, needs only four measurement rounds and there is
no constraint on the frequency response or the timing jitter of the detectors.
This can be compared to an efficient QST, as the required number of resources
does not scale exponentially with the system dimension [16].

##  IV Simulations

In this section we provide simulations for the proposed protocol in a
simulated quantum computer using the Qiskit package [17]. The basic idea is to
use the equivalence between the HOM effect and the so-called Swap Test [18],
which has already been studied in [19, 20] for single qubits, i.e., for a
single degree of freedom, but also for multimode input states [21], i.e., a
bi-partite entangled state. Indeed, a HOM interference effect between two pure
polarization states is equivalent to asking “are the two polarization states
identical?”, which, in its turn, is the question answered by the projection
over the singlet state $\ket{\psi^{-}}$.

Before performing the experiments, 10000 states over the Bloch Sphere were
randomly selected to create an uniform input data for all assessments.

###  IV.1 Polarized single photon states

Figure 3: Swap Test quantum circuit using a Toffoli gate. By measuring the
ancilla qubit in mode C, it is possible to determine whether states in modes A
and B are identical, which mimics the statistics of a HOM interferometer.
Figure adapted from Ref. [20]

.

In the case of Fock states ($n=1$) in pure polarization states, the HOM
interferometer, presented in Fig. 1, is equivalent to a standard Swap Test, as
shown in Fig. 3. In our case, qubit A corresponds to state $\ket{\psi}$ and
qubit B to state $U\ket{\psi}$. Whenever qubits A and B are identical (which
happens when $U=I$), measurement of the ancilla qubit C always result in a
projection onto state $\ket{0}$:

$Prob(``0")=\frac{1}{2}(1+|\braket{\psi}{U}{\psi}|^{2})=100\%$ (16)

which is equivalent to a coincidence measurement $P_{coinc}(I)$ in a HOM
scenario.

As presented in Fig. 3, in the simulation we prepare the aforementioned
arbitrary states, with previously known Stokes parameters, and use the method
to estimate $P_{coinc}^{exp}(\sigma_{j})$. The random states are obtained by a
$U_{init}$ operator, comprised of a $R_{Y}(\theta)$ and $R_{Z}(\phi)$ gates,
where $\theta$ and $\phi$ are calculated according to the random state’s
Stokes vector:

$\displaystyle\overrightarrow{s}$ $\displaystyle=(s_{1},s_{2},s_{3})$
$\displaystyle=DOP(\cos\theta,\cos\phi\sin\theta,\sin\phi\sin\theta)$ (17)

Note that, for simplicity, we keep the original definition of the Stokes
parameters such that
$s_{1}=\braket{\psi}{Z}{\psi},s_{2}=\braket{\psi}{X}{\psi}$ and
$s_{3}=\braket{\psi}{Y}{\psi}$. Additionally, in this case, Eq. 17 will have
$DOP=1$ for all randomly selected states - in the next section we will deal
with partially polarized light.

We now define the Stokes vector error estimation parameter $\varepsilon$ in
the Eq. 18, where the first term corresponds to the expected value for
$P_{coinc}(\sigma_{j})$, as portrayed in Eq. 7. It is worth mentioning that
for this experiment and the following one, which are not comprised of external
entanglement, we expect to find near-zero values for $P_{coinc}^{exp}(I)$.

$\displaystyle\varepsilon\equiv\sum_{j=1}^{3}\left|\frac{1-s_{j}^{2}}{2}-P_{coinc}^{exp}(I)-P_{coinc}^{exp}(\sigma_{j})\right|^{2}$
(18)

The estimated error according to Eq. 18 for each arbitrary state is depicted
in Fig. 4. It is perceivable that our method is reliable, regardless of the
quantum state at hand, as there is no correlation between error and position
in the Bloch Sphere.

Figure 4: Heatmap scatter plot of the proposed method’s error $\varepsilon$,
as defined in Eq. 18, versus the polar coordinates of the input state. For the
pure state input considered in this Section, all states lie on the shell of
the Poincaré Sphere, which enables this representation.

###  IV.2 Single photon states with internal entanglement

Now we consider the case of two internal degrees of freedom, such as in the
example of Fig. 2. In this case, we employ the circuit shown in Fig. 5.
Without loss of generality, we can consider the cases where the states are
given by, up to a global unitary operation:

$\displaystyle\ket{\psi}_{A}=$
$\displaystyle\alpha_{0}\ket{00}+\alpha_{1}\ket{11}$
$\displaystyle\ket{\phi}_{B}=$
$\displaystyle\beta_{0}\ket{00}+\beta_{1}\ket{11}$ (19)

where $|\alpha_{0}|^{2}+|\alpha_{1}|^{2}=1$ and
$|\beta_{0}|^{2}+|\beta_{1}|^{2}=1$. It is possible to show, using the results
from Foulds et al [21], that the probability of obtaining a result “01” or
“10” on the measurement of the ancillas is given by

$\text{Prob}(``01",``10")=\frac{1}{2}|\alpha_{0}\beta_{1}-\alpha_{1}\beta_{0}|^{2}$
(20)

Note that, in agreement with the HOM interferometer, in Fig. 1, whenever
qubits A and B are identical ($\alpha_{i}=\beta_{i}$), the probability in Eq.
20 is zero, which corresponds to the zero coincidence probability. Moreover,
if A and B are mutually orthogonal
($\alpha_{0}=\beta_{1}^{*},\alpha_{1}=-\beta_{0}^{*}$) then the probability
becomes 1/2, i.e., the photons are completely distinguishable.

The formula for the error estimation parameter $\varepsilon$ from Eq. 18 was
also applied to this experiment, with a small adaptation. In the first
experiment, only pure states were considered, while this case concerns mixed
states (from the point of view of the polarization degree of freedom). In
order to generate such states, we decreased the norm of every random pure
state, i.e. a Stokes vector with unit norm. This was performed by multiplying
the vector by the DOP. The resulting values of the Stokes parameters $s_{j}$
were then obtained as follows:

$\displaystyle s_{j}=$ $\displaystyle s^{pure}_{j}(DOP_{theory}),\text{where}$
(21) $\displaystyle DOP_{theory}=$ $\displaystyle\sqrt{1-4\text{det}(\rho)}$
(22)

where $s_{j}^{pure}$ are the coordinates of the initial random Bloch vector
and $\rho$ is the reduced density matrix tracing over all other degrees of
freedom other than polarization. The results are shown in Fig. 6, which
portrays the resulting mean quadratic error for different DOP values. Each
point in this graph corresponds to an average taken over 10000 points with
30000 measurement rounds ($\\#shots*3$) for each measurement round of each
point.

Figure 5: Swap Test quantum circuit for two-mode inputs. Each degree of
freedom is simulated by a qubit. This circuit uses two ancilla qubits, and the
probability of obtaining a result of “01” or “10” is equivalent to a
coincidence measurement in a HOM interferometer. Adapted from Ref. [21].
Figure 6: Mean quadratic polarimetry error, simulated in a quantum computer
emulator using the schematic of Fig. 5, as a function of the module of the
squared reduced density matrix of the input states. The mean was calculated
over the 10000 random states. As demonstrated, the proposed polarimetry method
is able to characterize the input state independently on the degree of
internal entanglement of the photons.

###  IV.3 Single photon states with external entanglement

In this section we deal with the situations where the incoming single photons
are mixed states, in the sense that the polarization states are entangled with
an external degree of freedom - the “environment”. For simplicity, we assume a
single-dimensional environment for each input qubit. The preparation procedure
of the states is very similar to the internal entanglement case, but the
measurement is identical to the first case (pure polarization states). The
setup can be found in Fig. 7.

Figure 7: Swap Test quantum circuit for single-mode inputs where each input is
entangled with an external and inaccessible degree of freedom (the
“environment”). Adapted from Ref. [20].

The quantum circuit of Fig. 7 is essentially the same one from Fig. 3, with
the addition of two qubits representing the environment. The probability of
measuring “0” in the ancilla qubit $C$ is equivalent to projecting the two-
qubit input state over the singlet state $\ket{\psi^{-}}$, such that

$\text{Prob}(``0")=\braket{\psi^{-}}{\rho_{A}\otimes\rho_{B}}{\psi^{-}}$ (23)

where $\rho_{A,B}$ are the reduced density matrices obtained by tracing over
the environment. Whenever the two input qubits are the same, which corresponds
to the situation where $U=I$, a simple calculation shows that, whenever
$\rho_{A}=\rho_{B}=\rho$, then

$\braket{\psi^{-}}{\rho\otimes\rho}{\psi^{-}}=\text{det}(\rho)$ (24)

which mimics the result previously given by Eq. 13.

Figure 8: Mean quadratic polarimetry error, simulated in a quantum computer
emulator using the schematic of Fig. 7, as a function of the module of the
squared reduced density matrix of the input states. The mean was calculated
over the 10000 randomly selected states. As demonstrated, the proposed
polarimetry method is able to characterize the input state independently on
the degree of external entanglement of the photons.

###  IV.4 Benchmarking with standard QST

The results shown in Figs. 4, 6 and 8 demonstrate that the proposed method
performs similarly independently on the input state; in other words, the
robustness of the method is validated against itself. In order to extend this
analysis, we introduce the standard quantum state tomography (QST) as a
reference for the performance. Without loss of generality, we perform an
extensive test using pure state inputs, i.e., those discussed in Section IV.1,
on the standard QST and the method depicted as a block diagram in Fig. 3. The
approach to the evaluation of the performance is the same: the input states
are varied to map different points on the shell of the Poincaré Sphere; but,
now, the number of measurement rounds (or realization of the same input state)
is also varied; for each number of measurement rounds, the error averaged over
all input states is computed following Eq. 18. The results, presented in Fig.
9, demonstrate that the error achieved by the proposed method and the standard
QST method is comparable, which validates the two-photon quantum state
tomography of photonic qubits.

It is worth noting that the results in Fig. 9 would not be attainable in
practice. For the standard QST, errors smaller than $1E-4$, would only be
achievable in case a polarizing beamsplitter (PBS) with an extinction ratio
larger than 40 dB was available, which is very far from actual commercial
values of $\sim$ 20-27 dB [22]. On the other hand, the proposed method of two-
photon polarimetry does not resort to polarization-selective components, but
the results correspond to a perfectly symmetrical beamsplitter (BS) being
employed. A deviation of about 0.5 dB is expected between the BS outputs;
however, this deviation can be compensated by adding the corresponding loss in
its less-affected output, meaning that the mean quadratic error $\varepsilon$
is only limited by calibration errors of the BS asymmetry, which can be made
as low as one requires.

Figure 9: Mean quadratic error for the 10000 randomly selected states,
according to the total number of measurement rounds ($\\#shots*3)$ performed
for each point. QST: Standard Quantum State Tomography. ST: Swap Test
(proposed method)

##  V Generalization of the method

Throughout the paper we have considered that the polarization state is to be
determined; however, the method can be equally applied to characterize any
two-level encoding of quantum information in single photons. The unitary
operators represented by $U$ in Fig. 1 can straightforwardly be replaced by
Pauli operators that act on any two-dimensional Hilbert space, henceforth
performing a characterization of any other degree of freedom, such as time-
bin, spatial mode [23], orbital angular momentum [24] or frequency encoding
[25]. Of course, the meaning of ”DOP” would have to be adjusted accordingly -
generic terms such as ”mutual coherence” may be employed for these other
cases, always corresponding to the norm of the Bloch/Stokes vector in a two-
dimensional Hilbert space.

Moreover, the “polarization-dependent loss” introduced in Appendix A would
have to be changed accordingly. For example, for time-bin qubits, a time-
dependent loss element would be needed. Again, the actual value of the loss
does not have any impact over the results.

##  VI Conclusion

We have presented a method for performing full quantum state tomography in
qubits encoded in single photons, such as the polarization degree of freedom,
that relies on the Hong-Ou-Mandel effect. By interfering the original quantum
state in a beamsplitter with the image of the input state by each of the three
Pauli spin operators, and by measuring the coincidence count rates between
single photon detectors placed at each beamsplitter output, the absolute
values of the Bloch/Stokes parameters can be obtained. By introducing three
additional measurements in rotated versions of the original state, the
information on the signs of the Bloch/Stokes parameters can be found.
Moreover, by simply interfering the unknown photon with a copy of itself, the
protocol is able to tell whether the polarization state is entangled with
another internal degree of freedom, such as time-bin, or entangled with an
external degree of freedom, as long as random time-varying unitary operations
or classical probability samplings can be ruled out. This is an advantage over
standard QST schemes that would only need to have access to these degrees of
freedom but also introduce additional measurements that scale exponentially
with the number of degrees of freedom under consideration. Simulations using
quantum circuits in a Swap-Test configuration show that the errors introduced
by the method are negligible, on the same order of magnitude as standard QST,
provided that a sufficiently large number of copies are measured.

For polarization qubits, we have shown that this method does not rely on
polarization-selective components, such as polarizers or polarizing
beamsplitters, which means that the measurements are not limited by the
extinction ratio of any such components. Therefore, we believe that the
presented method can be useful in measuring the degree of polarization of very
pure states.

###### Acknowledgements.

G. P. Temporão and T. B. Guerreiro acknowledge financial support from FAPERJ,
FAPESP and CNPq.

## References

  * Gisin and Thew [2007] N. Gisin and R. Thew, Nature Photonics 1, 165 (2007).
  * Couteau  _et al._ [2023] C. Couteau, S. Barz, T. Durt, T. Gerrits, J. Huwer, R. Prevedel, J. Rarity, A. Shields, and G. Weihs, Nature Reviews Physics 5, 354 (2023).
  * O’Brien [2007] J. L. O’Brien, Science 318, 1567 (2007).
  * Altepeter  _et al._ [2005] J. Altepeter, E. Jeffrey, and P. Kwiat (Academic Press, 2005) pp. 105–159.
  * Resch  _et al._ [2005] K. J. Resch, P. Walther, and A. Zeilinger, Phys. Rev. Lett. 94, 070402 (2005).
  * Takesue and Noguchi [2009] H. Takesue and Y. Noguchi, Opt. Express 17, 10976 (2009).
  * Titchener  _et al._ [2018] J. G. Titchener, M. Gräfe, R. Heilmann, A. S. Solntsev, A. Szameit, and A. A. Sukhorukov, npj Quantum Information 4, 19 (2018).
  * Hong  _et al._ [1987] C. K. Hong, Z. Y. Ou, and L. Mandel, Phys. Rev. Lett. 59, 2044 (1987).
  * Sgobba  _et al._ [2023] F. Sgobba, D. K. Pallotti, A. Elefante, S. Dello Russo, D. Dequal, M. Siciliani de Cumis, and L. Santamaria Amato, Photonics 10 (2023).
  * Harnchaiwat  _et al._ [2020] N. Harnchaiwat, F. Zhu, N. Westerberg, E. Gauger, and J. Leach, Opt. Express 28, 2210 (2020).
  * Cortes  _et al._ [2022] C. L. Cortes, P. Lefebvre, N. Lauk, M. J. Davis, N. Sinclair, S. K. Gray, and D. Oblak, Physical Review Applied 17, 034067 (2022).
  * Huang  _et al._ [2022] H.-Y. Huang, M. Broughton, J. Cotler, S. Chen, J. Li, M. Mohseni, H. Neven, R. Babbush, R. Kueng, J. Preskill, and J. R. McClean, Science 376, 1182 (2022).
  * Amaral and Temporão [2019] G. C. Amaral and G. P. Temporão, Quantum Information Processing 18, 1 (2019).
  * Marcikic  _et al._ [2003] I. Marcikic, H. de Riedmatten, W. Tittel, H. Zbinden, and N. Gisin, Nature 421, 509 (2003).
  * Jing  _et al._ [2019] B. Jing, X.-J. Wang, Y. Yu, P.-F. Sun, Y. Jiang, S.-J. Yang, W.-H. Jiang, X.-Y. Luo, J. Zhang, X. Jiang, _et al._ , Nature Photonics 13, 210 (2019).
  * Cramer  _et al._ [2010] M. Cramer, M. B. Plenio, S. T. Flammia, R. Somma, D. Gross, S. D. Bartlett, O. Landon-Cardinal, D. Poulin, and Y.-K. Liu, Nature Communications 1, 149 (2010).
  * Qiskit contributors [2023] Qiskit contributors, Qiskit: An open-source framework for quantum computing (2023).
  * Buhrman  _et al._ [2001] H. Buhrman, R. Cleve, J. Watrous, and R. de Wolf, Phys. Rev. Lett. 87, 167902 (2001).
  * Garcia-Escartin and Chamorro-Posada [2013] J. C. Garcia-Escartin and P. Chamorro-Posada, Phys. Rev. A 87, 052330 (2013).
  * Ripper  _et al._ [2023] P. Ripper, G. Amaral, and G. Temporão, Quantum Information Processing 22, 220 (2023).
  * Foulds  _et al._ [2021] S. Foulds, V. Kendon, and T. Spiller, Quantum Science and Technology 6, 035002 (2021).
  * Calliari  _et al._ [2019] F. Calliari, P. Tovar, C. Nascimento, B. Perlingeiro, G. Amaral, and G. T. ao, Appl. Opt. 58, 4395 (2019).
  * Ren  _et al._ [2013] B.-C. Ren, F.-F. Du, and F.-G. Deng, Phys. Rev. A 88, 012302 (2013).
  * Khoury and Milman [2011] A. Z. Khoury and P. Milman, Phys. Rev. A 83, 060301 (2011).
  * Lu  _et al._ [2019] H.-H. Lu, J. M. Lukens, B. P. Williams, P. Imany, N. A. Peters, A. M. Weiner, and P. Lougovski, npj Quantum Information 5, 24 (2019).

##  Appendix A Protocol for full quantum state tomography

It remains to show how one can obtain information on the signs of the Stokes
parameters; indeed, the protocol described so far is able to only measure
$|s_{j}|$, as shown in Eq. 7. Graphically, this would mean a restriction to
the octant $(s_{1}>0,s_{2}>0,s_{3}>0)$ in Poincaré sphere. There is a way,
however, to circumvent this limitation and obtain full information on the
Stokes parameters: the first step is increasing the number of measured
observables. Instead of only measuring $(I,\sigma_{1},\sigma_{2},\sigma_{3})$
as before, we need to add three more measurements. There are infinitely many
solutions, and one of them is depicted in Fig. 10.

Figure 10: Method for obtaining the signs of Stokes parameters. Originally,
the projection of the measured polarization state on the $(s_{2},s_{3})$ plane
could be in any of the four locations shown in red. A small rotation angle
$\theta$ around the $s_{1}$ axis is introduced on both BS inputs and now the
four images of the previous possibilities are shown in blue. Depending on the
change of the absolute value of $(s_{2},s_{3})$ one can rule out two of the
four possibilities, effectively obtaining the sign of the product
$s_{2}s_{3}$. Repeating the same reasoning for rotations around one of the
other axes, together with the knowledge of the sign of $s_{1}$ (see text for
details), suffices to determine all signs.

Fig. 10 shows the projection on the $(s_{2},s_{3})$ plane of the measured
polarization state $\ket{\psi}$. As there is no information on the signs of
the Stokes parameters, all four red dots are equally likely. Now, we introduce
a small rotation angle $\theta$ around the $s_{1}$ axis, for both BS inputs,
in the counter-clockwise direction, resulting in the state
$U(\theta)\ket{\psi}$ \- which, again, has four possibilities depending on the
signs of $(s_{2},s_{3})$. Now, we compare the measured values of
$(s_{2},s_{3})$ pre- and post-rotation. If $s_{2}$ decreases and $s_{3}$
increases, we are in the first or third quadrant, whereas if $s_{2}$ increases
and $s_{3}$ decreases, we can be sure we are in the second or fourth
quadrants. Therefore, we have eliminated two out of four possible cases - in
fact, we have determined the sign of the $s_{2}s_{3}$ product. The angle
$\theta$ should be selected with care, in order to avoid mapping one of the
four red points into another red point. For this purpose, the angle $\theta$
should not be fixed, bur rather be a function of the measured Stokes
parameters. Let $\xi\equiv\text{tan}^{-1}(|s_{3}|/|s_{2}|)$, as depicted in
Fig. 10. It suffices to select $\theta$ given by:

$\displaystyle\theta\text{ }$
$\displaystyle=\frac{\pi}{4}-\frac{\xi}{2},\xi<\pi/4$ (25)
$\displaystyle=-\frac{\xi}{2},\xi\geq\pi/4$

where the rotation is positive in the counterclockwise direction. Note that
$\pi/8\leq|\theta|\leq\pi/4$. Such a choice for $\theta$ will never result in
redundancies, as the rotation will never result in a quadrant change. Then we
have:

$\text{sign}(s_{2}s_{3})=\left\\{\begin{array}[]{ c l }+1&\quad\textrm{if
}|s_{2}|\textrm{ increases with }\theta\\\
-1&\quad\textrm{otherwise}\end{array}\right.$ (26)

If we repeat the same procedure introducing rotations around the other
Poincaré sphere axes, we will obtain the signs of all products
$s_{1}s_{2},s_{1}s_{3},s_{2}s_{3}$; however, this is still insufficient, as
the sign of $s_{2}s_{3}$ can be determined from the knowledge of the signs of
$s_{1}s_{2}$ and $s_{1}s_{3}$. In other words, there is a system of three
equations and three variables, but one of the equations is linearly dependent
of the other two. Indeed, we still have a redundancy of a global factor of
$\pm 1$ in the Stokes vector, which means we don’t know whether the input
polarization state is $\ket{\phi}$ or $\ket{\phi^{\perp}}$.

For this reason, we introduce a polarization-dependent loss (PDL) in one of
the modes, e.g. in front of detector $SPD_{0}$, as shown in Fig. 1. This PDL
element should be aligned such that its axes coincide with the horizontal and
vertical polarization directions - for example, with a transmission
coefficient $\eta_{H}$ for $\ket{H}$ different from the value $\eta_{V}$
associated with polarization $\ket{V}$. This addition will change the
probability of single clicks on $SPD_{0}$, depending on whether the incoming
photons have positive or negative values of Stokes parameter $s_{1}$, thus
providing the missing information for full state characterization. Note that
the actual value of the PDL (i.e., the extinction ratio of the polarizer)
plays no role in the calculations of the Stokes parameters.

In order to illustrate the effect of the PDL, let $C_{i}$ be the single counts
in detector $SPD_{i}$ and $C_{01}$ be the coincidente counts during the
detector’s integration time window. Now let $n$ be the number of photon pairs
that have impinged on the beamsplitter during the detection time window under
consideration. We have:

$\displaystyle C_{0}=$
$\displaystyle\frac{n}{2}[1-(1-\eta_{0})^{2}]\eta_{PDL}$ $\displaystyle
C_{1}=$ $\displaystyle\frac{n}{2}[1-(1-\eta_{1})^{2}]$ $\displaystyle C_{01}=$
$\displaystyle nP_{coinc}\eta_{0}\eta_{1}\eta_{PDL}$ (27)

where $P_{coinc}$ is the probability of ”bunching” in the BS, which is given
by Eq. 2, $\eta_{0(1)}$ is the quantum efficiency of $SPD_{0(1)}$ and
$\eta_{PDL}$ is the (average) transmission coefficient of the PDL element.
Recalling that the PDL has transmissions $\eta_{H}$ and $\eta_{V}$ in the
horizontal and vertical polarizations, respectively, then:

$\eta_{PDL}=\eta_{H}|\braket{\psi}{H}|^{2}+\eta_{V}|\braket{\psi}{V}|^{2}$
(28)

Note that the horizontal and vertical polarizations can be distinguished by
measuring the ratio $C_{0}/C_{1}$, i.e., the single counts in the detectors.
This provides enough information for determination of the sign of Stokes
parameter $s_{1}$: it suffices to compare $\eta_{PDL}$ with the average value
of the horizontal and vertical transmission coefficients:

$\text{sign}(s_{1})=\left\\{\begin{array}[]{ c l }+1&\quad\textrm{if
}\eta_{PDL}\geq(\eta_{H}+\eta_{V})/2\\\
-1&\quad\textrm{otherwise}\end{array}\right.$ (29)

where $\eta_{H}>\eta_{V}$ was chosen without loss of generality. Note that in
the equality case that the sign is irrelevant as $s_{1}=0$.

In summary, the protocol works in the following way: first off, we measure the
absolute values of the Stokes parameters $|s_{j}|$ by measuring the
coincidence rates according to Eq. 7, in each case choosing $U=\sigma_{j}$;
then we proceed by calculating two angles
$\xi_{1}\equiv\text{tan}^{-1}(|s_{3}|/|s_{2}|)$ and
$\xi_{2}\equiv\text{tan}^{-1}(|s_{3}|/|s_{1}|)$. Using Eq. 25, we calculate
the required angles of rotation around each axis - $R_{1}(\theta_{1})$ and
$R_{2}(\theta_{2})$ \- and apply the same rotation in both inputs, repeating
the measurements of $\sigma_{1}$ and $\sigma_{2}$. By calculating the single
counts ratio $C_{0}/C_{1}$ we have the sign of $s_{1}$; combining this
information with the increase or decrease of the Stokes parameters after the
rotations $R_{1}(\theta_{1})$ and $R_{2}(\theta_{2})$, according to Eq. 26, we
finally obtain the signs of all Stokes parameters and the protocol is
finished.

##  Appendix B  Calculation of coincidence rates

In this appendix we provide calculations for the coincidence rate in Eq. (2)
and the coincidence probability when the input state is given by Fig. 2.

Let $a^{\dagger}(\psi)$ and $b^{\dagger}(\psi)$ be the bosonic creation
operators for the two input modes of a symmetrical beam splitter. The BS
transformation reads,

$\displaystyle a^{\dagger}(\psi)$ $\displaystyle\rightarrow$
$\displaystyle\frac{a^{\dagger}(\psi)+ib^{\dagger}(\psi)}{\sqrt{2}}$ (30)
$\displaystyle b^{\dagger}(\psi)$ $\displaystyle\rightarrow$
$\displaystyle\frac{b^{\dagger}(\psi)+ia^{\dagger}(\psi)}{\sqrt{2}}$ (31)

Modes $a$ and $b$ then transform according to,

$\displaystyle
a^{\dagger}(\psi)b^{\dagger}(\psi^{\prime})\rightarrow\frac{1}{2}\left(\underbrace{ia^{\dagger}(\psi)a^{\dagger}(\psi^{\prime})+ib^{\dagger}(\psi)b^{\dagger}(\psi^{\prime})}_{\textrm{(i)
no coincidences}}\right.$
$\displaystyle\left.\underbrace{a^{\dagger}(\psi)b^{\dagger}(\psi^{\prime})-b^{\dagger}(\psi)a^{\dagger}(\psi^{\prime})}_{\textrm{(ii)
possible coincidences}}\right)$ (32)

Note the first two terms do not contribute to the coincidence rate, while the
remaining ones do. Since,

$\displaystyle|\psi\rangle=\sqrt{\mathcal{F}}|\psi^{\prime}\rangle+\sqrt{1-\mathcal{F}}e^{i\varphi}|\psi^{\prime}_{\perp}\rangle$
(33)

where $\mathcal{F}=\mathcal{F}(U)$, we may write the same relation in second-
quantization notation,

$\displaystyle a^{\dagger}(\psi)$ $\displaystyle=$
$\displaystyle\sqrt{\mathcal{F}}a^{\dagger}(\psi^{\prime})+\sqrt{1-\mathcal{F}}e^{i\varphi}a^{\dagger}(\psi^{\prime}_{\perp})$
(34) $\displaystyle b^{\dagger}(\psi)$ $\displaystyle=$
$\displaystyle\sqrt{\mathcal{F}}b^{\dagger}(\psi^{\prime})+\sqrt{1-\mathcal{F}}e^{i\varphi}b^{\dagger}(\psi^{\prime}_{\perp})$
(35)

Substituting these relations in Eq. (32) we find for the (ii) terms,

$\displaystyle\frac{\sqrt{\mathcal{F}}}{2}\left(\underbrace{a^{\dagger}(\psi^{\prime})b^{\dagger}(\psi^{\prime})-b^{\dagger}(\psi^{\prime})a^{\dagger}(\psi^{\prime})}_{\textrm{interference}}\right.$
$\displaystyle\left.\frac{\sqrt{1-\mathcal{F}}}{2}e^{i\varphi}\underbrace{a^{\dagger}(\psi^{\prime}_{\perp})b^{\dagger}(\psi^{\prime})-b^{\dagger}(\psi^{\prime}_{\perp})a^{\dagger}(\psi^{\prime})}_{\textrm{no
interference}}\right)$ (36)

Coincidences arise from non-interfering terms, hence we have

$\displaystyle
P_{coinc}=|\pm\frac{1}{2}\sqrt{1-\mathcal{F}}e^{i\varphi}|^{2}\times
2=\frac{1-\mathcal{F}}{2}$ (37)

Now we proceed to the calculation of the coincidence rate for the internal
entanglement case. Consider the interference of two photons, one in state
$\ket{\psi}$ and the other in state $(U\otimes I)\ket{\psi}$, where $I$ is the
identity operator acting on the time-bin Hilbert space. The state after the BS
will be given by:

$\ket{\psi}_{01}=\left[\frac{i\ket{\psi}_{0}+\ket{\psi}_{1}}{\sqrt{2}}\right]\\!\otimes\\!\left[\frac{(U\otimes
I)\left(\ket{\psi}_{0}+i\ket{\psi}_{1}\right)}{\sqrt{2}}\right]$ (38)

where the subscripts 0 and 1 correspond to the spatial modes where detectors
$SPD_{0}$ and $SPD_{1}$ are located, respectively. Considering
$\ket{\psi}=\alpha\ket{H}\ket{t_{0}}+\beta\ket{V}\ket{t_{1}}$ as in Fig. 2 and
replacing in Eq. 38, we obtain an expression comprised of 16 terms from all
possible combinations of spatial modes, polarization states and time bins,
which is given by, up to a normalization constant:

$\displaystyle\ket{\psi}_{01}$ $\displaystyle=\text{
}i\alpha^{2}\ket{H,t_{0}}_{0}\ket{U(H),t_{0}}_{0}+i\alpha\beta\ket{H,t_{0}}_{0}\ket{U(V),t_{1}}_{0}+i\alpha\beta\ket{V,t_{1}}_{0}\ket{U(H),t_{0}}_{0}+i\beta^{2}\ket{V,t_{1}}_{0}\ket{U(V),t_{1}}_{0}$
(39)
$\displaystyle-\alpha^{2}\ket{H,t_{0}}_{0}\ket{U(H),t_{0}}_{1}-\alpha\beta\ket{H,t_{0}}_{0}\ket{U(V),t_{1}}_{1}-\alpha\beta\ket{V,t_{1}}_{0}\ket{U(H),t_{0}}_{1}-\beta^{2}\ket{V,t_{1}}_{0}\ket{U(V),t_{1}}_{1}$
$\displaystyle+\alpha^{2}\ket{U(H),t_{0}}_{0}\ket{H,t_{0}}_{1}+\alpha\beta\ket{U(V),t_{1}}_{0}\ket{H,t_{0}}_{1}+\alpha\beta\ket{U(H),t_{0}}_{0}\ket{V,t_{1}}_{1}+\beta^{2}\ket{U(V),t_{1}}_{0}\ket{V,t_{1}}_{1}$
$\displaystyle+i\alpha^{2}\ket{H,t_{0}}_{1}\ket{U(H),t_{0}}_{1}+i\alpha\beta\ket{H,t_{0}}_{1}\ket{U(V),t_{1}}_{1}+i\alpha\beta\ket{V,t_{1}}_{1}\ket{U(H),t_{0}}_{1}+i\beta^{2}\ket{V,t_{1}}_{1}\ket{U(V),t_{1}}_{1}$

where the notation $\ket{\psi,t_{1}}\equiv\ket{\psi}\ket{t_{i}}$ has been
employed for simplicity, and $U(H)/U(V)$ are simplified notations for denoting
the image of the unitary operation on the H/V polarization states.

Note that the first four and last four terms in Eq. 39 correspond to the cases
where both photons are found in the same detector, whereas the remaining eight
middle terms correspond to the cases where one photon is found at each
detector. In the case where $U=I$, note that the eight middle terms cancel
each other out, which is exactly the bunching effect that is expected in such
case; we will come back to this result later.
In the case where $U=\sigma_{1}$, which corresponds to the measurement of
Stokes parameter $s_{1}$, we have $U(H)=H$ and $U(V)=-V$, which leads to the
cancellation of several terms in Eq. 39, particularly the terms with
coefficients $\pm\alpha^{2}$, $\pm\beta^{2}$ and $i\alpha\beta$. Therefore,
the coincidence probability $P_{coinc}(\sigma_{1})$ is given by:

$P_{coinc}(\sigma_{1})=\frac{4|\alpha|^{2}|\beta|^{2}}{2|\alpha|^{4}+2|\beta|^{4}+4|\alpha|^{2}|\beta|^{2}}$
(40)

Now replacing in Eq. 7 and using $|\alpha|^{2}+|\beta|^{2}=1$, we finally
obtain:

$s_{1}^{2}=(2|\alpha|^{2}-1)^{2}$ (41)

which coincides with the value obtained by standard quantum state tomography.
Indeed, when $\alpha=\beta=1/\sqrt{2}$, we obtain $s_{1}$ = 0 and
$P_{coinc}(\sigma_{1})=1/2$ as expected, since $\ket{\psi}$ and
$\sigma_{1}\ket{\psi}$ become mutually orthogonal. For any value of $\alpha$,
on the other hand, we have $s_{2}=s_{3}=0$.


# Extractive Summarization of Related Bug-fixing Comments in Support of Bug
Repair

Rrezarta Krasniqi
Dept. of Computer Science and Engineering
University of Notre Dame
Notre Dame, IN, USA
<EMAIL_ADDRESS>
###### Abstract

When developers investigate a new bug report, they search for similar
previously fixed bug reports and discussion threads attached to them. These
discussion threads convey important information about the behavior of the bug
including relevant _bug-fixing comments_. Often times, these discussion
threads become extensively lengthy due to the severity of the reported bug.
This adds another layer of complexity, especially if relevant bug-fixing
comments intermingle with seemingly unrelated comments. To manually detect
these relevant comments among various cross-cutting discussion threads can
become a daunting task when dealing with high volume of bug reports. To
automate this process, our focus is to initially extract and detect comments
in the context of _query relevance_ , the use of _positive language_ , and
_semantic relevance_. Then, we merge these comments in the form of a summary
for easy understanding. Specifically, we combine Sentiment Analysis, and the
TextRank Model with the baseline Vector Space Model (VSM). Preliminary
findings indicate that bug-fixing comments tend to be positive and there
exists a semantic relevance with comments from other cross-cutting discussion
threads. The results also indicate that our combined approach improves overall
ranking performance against the baseline VSM.

##  I Introduction

A “bug fixing” comment is a comment in a conversation thread attached to a bug
report that describes the bug fix. When developers report bugs via issue
tracking systems, the conversations between the end-users and developers are
presented as a collection of threads. When a fix is communicated, the person
who has made the fix or recommends a fix often concludes the conversation with
a more-positive language that summarizes the problems and the repairs. Recent
studies have indicated that sentiment patterns were noticeable in open-source
bug report discussion threads [10, 4]. We also observed, that positive
sentiment patterns were noticeable when bug reports were concluded as ‘fixed’.
Our broader objective is to automate this process suitably for large-scale
open-source platforms. However, there are two emerging factors that need to be
taken into account when dealing with open-source platforms [6, 5, 8]. The most
pressing ones span across two directions, primarily time dimension and content
dimension. When dealing with the former one, studies showed that open-source
platforms were plagued with thousands of bug reports daily [1, 13]. Due to
this sheer volume of bugs, it becomes prohibitively time consuming for the
developers to fix these bugs efficiently and effectively [11]. When dealing
with the latter one, a recent qualitative study conducted by Arya _et_. al [2]
showed that some of these issue discussion threads over time become extremely
lengthy and complex to comprehend because both developers and end-users carry
different backgrounds. Consequently, this communication scenario leads to
lengthy discussions. In hindsight, the content factor poses a challenge to
developers who must reason which information hidden within these lengthy
discussion threads is relevant and useful for finding the root cause for the
new bugs. This adds another layer of complexity, especially if relevant bug-
fixing comments intermingle with seemingly unrelated comments. Motivated by
these observations, this work presents a three-pronged approach that
recommends bug-fixing comments extracted from crosscutting issue discussion
threads that are beneficial for recommending a bug fix. These bug-fixing
comments are analysed and extracted by considering _user query relevance_ ,
_positive language_ , and _semantic relevance_. Specifically, we combine
Sentiment Analysis (SA), and the TextRank Model (TR) with the baseline Vector
Space Model (VSM) as employed by Zhou et _al_. [16]. We use SA to detect
positive sentiments in the comments. We then use the TR heuristic to build the
semantic connections amongst similar related comments from those cross-cutting
discussion threads.

##  II Overview of Approach

Our approach recommends comments extracted from issue-tracking cross-cutting
discussion threads in three steps. First, it uses the baseline VSM to retrieve
user query-related comments with initial keyword scores. Second, it uses
Sentiment Analysis (SA) to compute sentiment keyword scores based on lookup
_bonus and penalty opinion lexicon_ , and re-rank comments written in a more
positive style from step-1. Finally, it uses meta-heuristic technique such as
TextRank (TR) to re-rank keywords based on their co-occurrence and their order
of importance from step-2 that are semantically connected. In sum, the above
steps represent a combined linear weighted function where keyword weights of
each comment are influenced from the combined scores obtained by VSM, SA, and
TR.

###  II-A RetroRank Tool

We have built a GUI-based tool that we refer to as RetroRank. In a nutshell,
RetroRank takes as an input _a user query_ (e.g., a set of keywords extracted
from bug’s title or bug’s long description) and returns as an output _a list
of recommended bug-fixing comments_ extracted from cross-cutting discussion
threads. RetroRank relies on MySQL database where it stores all OSS bug
reports and bug repositories. RetroRank builds upon two existing packages.
_Tkinter_ is a standard GUI library that is used to build the GUI framework.
_Sklearn_ is another library that is used to build the underlying
functionalities of our approach. Broadly speaking, RetroRank is designed to
adapt to any project that supports modern development practices. The inclusion
of ‘pre-merge’ mechanism is an example where relevant comments can be used as
part of code review [7, 12].

TABLE I: Statistical summary of the results. Value _n_ denotes the number of
bugs evaluated in terms of ranking performance. $\mu$ denotes average ranking
position obtained by each configuration. The rest represent Student’s Paired
t-Test metrics.

Metric | Approach | _n_ | $\mu$ | _p_ | _t_ | _t_crit_ | Decision
---|---|---|---|---|---|---|---
Config-1 |  | VSM+SA+TR
---
VSM+SA
25 |  | 1.8
---
3.4
2.8E-05 | -4.812 | 2.0301 | Reject
Config-2 |  | VSM+SA+TR
---
VSM+TR
25 |  | 1.8
---
3.7
2.9E-06 | -5.557 | 2.0301 | Reject
Config-3 |  | VSM
---
VSM+TR
25 |  | 9.1
---
3.7
1.3E-09 | 8.146 | 2.0638 | Reject
Config-4 |  | VSM
---
VSM+SA
25 |  | 9.1
---
3.4
2.0E-09 | 8.004 | 2.0638 | Reject
Config-5 |  | VSM
---
VSM+SA+TR
25 |  | 9.1
---
1.8
3.0E-11 | 9.513 | 2.0638 | Reject

##  III Evaluation Strategy

###  III-A Preliminary Synthetic Study

In the synthetic study, we analyzed $25$ real bugs to compare our approach
against several configurations. Our evaluation strategy employed four steps.
First, we manually identified the goldset of bugs and bug-fixing comments.
Second, we recruited 12 developers to create ‘search queries’ for new bugs.
Third, we used those ‘user created queries” from the previous step to run each
configuration. Finally, based on the results retrieved from each
configuration, we counted and marked the ranking position where the goldset
(i.e., bug-fixing comments from past resolved bugs) appeared in each
configuration’s retrieved list. Due to space limitation, we only reported the
significance of ranking performed of each configuration as denoted in Table I,
where $\mu$ denotes the average ranking obtained by each configuration. We
plan to extend this work by fully reporting its findings.

###  III-B Preliminary Results: Overall Ranking Performance

Preliminary results indicate that VSM+SA+TR achieved the highest performance,
followed by VSM+SA, VSM+TR, and the baseline VSM as employed by Zhou et. al
[16]. Findings in Table I showed that the average ranking position $\mu$ of
the recommended comment for VSM+SA+TR was $1.8$, whereas for the VSM was
$9.1$. This indicates, VSM+SA+TR placed the recommended comment on average
around first position, versus VSM which placed it around the ninth position.
We also noted that both VSM+SA and VSM+TR ranked in a higher position than the
baseline VSM. Overall, results showed that differences in ranking position
were statistically significant as reported in Table I, H5 ($3.0$E$-11$) with
p-value of $0.05$ and a confidence level of $0.95$. Student’s Paired t–Test
[14] was used as a primary metric as done in other studies [9, 15, 3].

##  IV Conclusion and Evaluation Plans

In this position paper, we presented a novel idea of how issue tracking cross-
cutting discussion threads can be used as the core content in support of bug
repair. As part of the evaluation plan, we will conduct a larger user study
where we will empirically compare the best-performing approach to the baseline
VSM. Our objective is to also measure comment(s) _relevance_ returned by each
approach. Additionally, we will perform a qualitative user-study where the
rationale behind our work will be explained in-depth.

## References

  * [1] J. Anvik, L. Hiew, and G. C. Murphy.  Coping with an open bug repository.  In Proceedings of the OOPSLA workshop on Eclipse tech., pages 35–39. ACM, 2005.
  * [2] D. Arya, W. Wang, J. L. Guo, and J. Cheng.  Analysis and detection of information types of open source software issue discussions.  In 2019 IEEE 41st International Conference on Software Engineering, pages 454–464. IEEE, 2019.
  * [3] N. Bettenburg, R. Premraj, T. Zimmermann, and S. Kim.  Duplicate bug reports considered harmful … really?  In 24th IEEE International Conference on Software Maintenance (ICSM 2008), September 28 - October 4, 2008, Beijing, China, pages 337–345, 2008.
  * [4] C. C. A. Blaz and K. Becker.  Sentiment analysis in tickets for it support.  In Proceedings of the 13th International Conference on Mining Software Repositories, pages 235–246, 2016.
  * [5] J. Feller, B. Fitzgerald, et al.  Understanding open source software development.  Addison-Wesley London, 2002.
  * [6] B. Fitzgerald.  The transformation of open source software.  MIS quarterly, pages 587–598, 2006.
  * [7] T. J. Halloran and W. L. Scherlis.  High quality and open source software practices.  In 2nd Workshop on Open Source Software Engineering, 2002.
  * [8] W. M. Ibrahim, N. Bettenburg, E. Shihab, B. Adams, and A. E. Hassan.  Should i contribute to this discussion?  In 2010 7th IEEE Working Conference on Mining Software Repositories (MSR 2010), pages 181–190. IEEE, 2010.
  * [9] C. Le Goues, M. Dewey-Vogt, S. Forrest, and W. Weimer.  A systematic study of automated program repair: Fixing 55 out of 105 bugs for $8 each.  In M. Glinz, G. C. Murphy, and M. Pezzè, editors, 34th International Conference on Software Engineering (ICSE), 2012, June 2-9, 2012, Zurich, Switzerland, pages 3–13. IEEE Computer Society, 2012.
  * [10] W. Maalej and H. Nabil.  Bug report, feature request, or simply praise? on automatically classifying app reviews.  In 2015 IEEE 23rd international requirements engineering conference (RE), pages 116–125. IEEE, 2015.
  * [11] L. Marks, Y. Zou, and A. E. Hassan.  Studying the fix-time for bugs in large open source projects.  In 7th International Conference on Predictive Models in Software Engineering, page 11. ACM, 2011.
  * [12] A. Mockus, R. T. Fielding, and J. D. Herbsleb.  Two case studies of open source software development: Apache and mozilla.  ACM Transactions on Software Engineering and Methodology (TOSEM), 11(3):309–346, 2002.
  * [13] M. Nurolahzade, S. M. Nasehi, S. H. Khandkar, and S. Rawal.  The role of patch review in software evolution: an analysis of the mozilla firefox.  In Proceedings on Principles of software evolution and software evolution workshops, pages 9–18. ACM, 2009.
  * [14] M. D. Smucker, J. Allan, and B. Carterette.  A comparison of statistical significance tests for information retrieval evaluation.  In Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, pages 623–632. ACM, 2007.
  * [15] S. Wang, D. Lo, L. Jiang, Lucia, and H. C. Lau.  Search-based fault localization.  In P. Alexander, C. S. Pasareanu, and J. G. Hosking, editors, 26th IEEE/ACM International Conference on Automated Software Engineering (ASE 2011), Lawrence, KS, USA, November 6-10, 2011, pages 556–559. IEEE Computer Society, 2011.
  * [16] J. Zhou, H. Zhang, and D. Lo.  Where should the bugs be fixed? more accurate information retrieval-based bug localization based on bug reports.  In Proceedings of 34th International Conference on Software Engineering, ICSE 2012, June 2-9, 2012, Zurich, Switzerland, pages 14–24, 2012\.


# Hyperdimensional Computing vs. Neural Networks: Comparing Architecture and
Learning Process

Dongning Ma, Student Member, IEEE, Xun Jiao, Member, IEEE Authors are with the
Department of Electrical and Computer Engineering of Villanova University,
Villanova, PA 19085. (e-mail: {dma2<EMAIL_ADDRESS>
###### Abstract

Hyperdimensional Computing (HDC) has obtained abundant attention as an
emerging non von Neumann computing paradigm. Inspired by the way human brain
functions, HDC leverages high dimensional patterns to perform learning tasks.
Compared to neural networks, HDC has shown advantages such as energy
efficiency and smaller model size, but sub-par learning capabilities in
sophisticated applications. Recently, researchers have observed when combined
with neural network components, HDC can achieve better performance than
conventional HDC models. This motivates us to explore the deeper insights
behind theoretical foundations of HDC, particularly the connection and
differences with neural networks. In this paper, we make a comparative study
between HDC and neural network to provide a different angle where HDC can be
derived from an extremely compact neural network trained upfront. Experimental
results show such neural network-derived HDC model can achieve up to 21% and
5% accuracy increase from conventional and learning-based HDC models
respectively. This paper aims to provide more insights and shed lights on
future directions for researches on this popular emerging learning scheme.

###### Index Terms:

hyperdimensional computing, neural network, non von Neumann computing, bio-
inspired computing

##  I Introduction

In recent years, machine learning has achieved tremendous success in a diverse
range of domains, even surpassing the capability of human beings. However,
such huge progress on machine learning comes with the drastically growing
model complexity and the ever-increasing computation resources [17]. On the
other hand, as machine learning has been continuously pushed to the edge such
as embedded systems or (near-)sensor devices, the computation resources
allocated for learning is significantly less than centralized servers or data
centers [15]. To address this challenge, researchers seek for non-conventional
computing paradigms, and Hyperdimensional Computing (HDC), is one example seen
as a promising alternative of conventional machine learning models [9]. The
key idea of HDC is to leverage the computing capabilities of distributed
representation of high dimensional numerical vectors referred to as
Hypervectors (HV) [6]. Specifically, HDC is formulated to leverage HVs and
their associated vector arithmetic to present, represent, and process
information from different modalities [19]. Related studies show that HDC is
able to achieve success on a diverse set of applications, including speech
recognition [5], human activity recognition [14, 8], NLP [18, 12] and anomaly
detection [20]. In addition, various acceleration techniques are also proposed
and implemented on heterogeneous platforms including GPGPU [8], FPGA [16] and
even in-memory architectures [7].

Although achieving energy efficiency and acceleration, one major obstacle
preventing HDC to be applied for a broader range of applications is its
relatively lower learning capability. For example, for a very basic benchmark
of MNIST, the baselines of HDC solutions can only achieve less than 95%
accuracy [13, 3], which is much lower than a basic LeNet-like network [11]. On
the other hand, the application datasets which HDC shows advantage on are
mostly small and relatively easier to differentiate. Therefore, such a limited
set of applications when evaluating HDC algorithm is unlikely to justify the
benefits of HDC and enable its practical use.

On the other hand, researchers endeavor to introduce techniques from neural
networks into HDC for performance enhancement. For example, a fixed random
connection neural network layer can be added into the HDC flow to achieve
better performance [2]. Perceptrons specific for HDC are also proposed and
further combined with other techniques such as drop-out [1]. HDC is also found
similar to binary neural networks based on which loss functions are also
defined so that HDC can be trained with back propagation [3]. Those related
works reveals deeper connections between HDC and neural network and also
motivate us to further explore the HDC foundations. This paper, specifically,
present a comparative study to show the similarities and differences between
HDC and neural networks. The main contributions are as follows:

  * •

We first present a recap of HDC preliminaries applied in the majority of
related works, which we recognize as the “canonical” HDC flow. We then make a
comparison between the HDC model and a two-layer “neural network”111Typically,
neural networks have at least 3 layers, however we recognize this two layers
of perceptrons as a “neural network” for explanatory purposes and use this
term throughout the paper., including both the architecture and the learning
process.

  * •

Experiments using two datasets of MNIST and CIFAR-10 show that HDC models can
be directly transformed from a neural network which outperforms SOTA HDC
models by 5% to 21% in accuracy. This paper provides an alternative angle to
assess the learning capabilities of HDC and insights on future directions of
enhancing and optimizing this promising computing scheme.

##  II Recap of HDC

###  II-A Notions of HDC

####  II-A1 Hypervector

Hypervector (HV) is the fundamental “building block” of HDC. HVs have three
most important properties. First, HVs are high dimensional numerical vectors,
which are usually higher than 10,000 dimensions where each dimension is a
number. This provides an extremely large space for HVs to represent
information. Second, the HVs are usually randomly initialized and the numbers
generated follows i.i.d. randomness. Because of the high dimensionality of
HVs, this can ensure that two randomly initialized HVs can be (almost)
orthogonal to each other. Third, HVs are holographic which means that within
an HV, all the dimensions are recognized equally as to their contributions and
there is no any dimension that is more important than others. In other words,
the HV needs to be treated as a whole and not micro-coded. An HV of $D$
dimensions can be denoted as Eq. 1, where $v_{d}$ is the number at the $d$-th
dimension.

$\vec{V}=(v_{1},v_{2},...,v_{D})$ (1)

####  II-A2 HDC operations

There are three types of HV operations that are most frequently used in HDC:
addition, multiplication and permutation and each type of operation has its
specific physical meaning:

  * •

Addition $+$: takes two HVs as operands and performs element-wise addition on
the numbers at the same dimension. Addition is usually used to aggregate the
information of two HVs from the same modality and create a superposition of
them.

  * •

Multiplication $\times$: also takes two HVs as operands but performs element-
wise multiplication on the numbers at the same dimension. Contrary to
addition, multiplication is usually used to combine information from different
modalities and create new information of another modality based on these two.

  * •

Permutation $\rho$: only takes one HV as the operand and perform cyclic
rotation (shift) over the HV. The shift amount can be configured based on
specific applications. Permutation is usually used to reflect temporal or
spatial patterns of information.

Note that all the three HV operations do not modify the dimension of HV
operands, i.e., the input and output HV of each operation are in the same
dimension.

####  II-A3 HDC memories

Memories in HDC are a specific cluster of HVs which serve different functions
in developing a model. Specifically, there are two types of memories: item
memory and associative memory. Item memory is related to the input data,
accommodates item HVs that are generated based on the input features. Assume
the input sample has $M$ modalities of features and each feature can have $N$
possible values, then the item memory of each modality of feature can be
generated as Eq. 2. On the other hand, associative memory is related to the
output of the model, namely making predictions. If the classification task has
$C$ classes, then the associative memory is configured as Eq. 3, in which each
HV $\vec{A_{c}}$ inside the memory is the representation of a class.
Associative memory is usually initialized with zero numbers.

$\mathbf{I}_{m}=\\{\vec{I_{1}},\vec{I_{2}},...\vec{I_{N}}\\}$ (2)

$\mathbf{A}=\\{\vec{A_{1}},\vec{A_{2}},...\vec{A_{C}}\\}$ (3)

####  II-A4 Similarity metrics

Since each HV represents a specific information, there is a natural need of
metrics that could represent the similarity between information that two HV
respectively accommodate. Hamming distance and cosine similarity are the two
mostly used similarity metrics. Hamming distance is for calculating the
similarity between binary or bipolar HVs while cosine similarity can be used
for HVs in different data types. We show the calculation of cosine similarity
$\delta_{cos}$ in Eq. 4 as an example. A higher similarity indicates that the
two HVs compared share more information in common.

$\displaystyle\delta_{cos}(\vec{V_{a}},\vec{V_{b}})=\frac{\vec{V_{a}}\cdot\vec{V_{b}}}{||\vec{V_{a}}||\times||\vec{V_{b}}||}$
(4)

###  II-B HDC Model Development

A canonical flow of developing an HDC model features four major phases:
Encoding, Training, Inference, and Retraining.

####  II-B1 Encoding

Encoding is the basic phase of HDC model development. During encoding, the
input samples are “encoded” into their representative HVs using a set of
application-dependent HD operations $\Phi$ and the item memories. For example
in Eq. 5, assume the input sample has $M$ features:
$\vec{F}=\\{f_{1},f_{2},...,f_{M}\\}$, the values of each feature $f_{m}$ is
used as indices to fetch corresponding item HV in the item memories
$\mathbf{I}_{m}$. After encoding, the realistic features are now in the form
of high-dimensional representations, namely the HVs which are used in all the
other three phases of model development.

$\vec{V}=\Phi(\mathbf{I}_{1}.index(f_{1}),\mathbf{I}_{2}.index(f_{2}),...,\mathbf{I}_{M}.index(f_{M}))$
(5)

####  II-B2 Training

Training is the phase where associative memory is trained using the encoding
HVs from the training samples. As noted in Eq. 6, all the sample HVs sharing
the same label $c$ are summed to the corresponding class HV $\vec{A_{c}}$ in
the associative memory. This is to collect and aggregate information to build
a representative HV for each class.

$\mathbf{A}=\\{\sum{\vec{A_{1}}},\sum{\vec{A_{2}}},...,\sum{\vec{A_{C}}}\\}$
(6)

####  II-B3 Inference

Inference is the phase where associative memory is used to predict the class
of unseen test samples. During inference, the unseen samples are still encoded
using the same item memory as training. The encoded HV of the unseen sample is
often referred to as the query HV $\vec{V_{?}}$. As shown in Eq. 7, the
similarity between query HV and every class HV in the associative memory is
calculated and the class with the highest similarity is then determined as the
predicted label $l$ for this unseen sample.

$l=\delta_{cos}(\vec{V_{?}},\mathbf{A}).argmax()$ (7)

####  II-B4 Retraining

Retraining is an optional phase of fine-tuning the trained associative memory
to achieve higher performance of model. During retraining, the model iterates
over the encoded training samples and make inference to obtain the prediction
labels using the trained associative memory. Then the prediction label is
compared with the ground truth label to identify if there is a discrepancy. If
so, the associative memory is updated as Eq. 8 describes: the encoded HV of
the sample is subtracted from the class HV of the wrong prediction and added
to the correct class. This is to reduce the wrong information from the mis-
classifications and instead enhance the information of the correct class.

$\displaystyle\vec{A}_{wrong}=\vec{A}_{wrong}-\vec{V}$ (8)
$\displaystyle\vec{A}_{correct}=\vec{A}_{correct}+\vec{V}$

In the following sections, we depart from the canonical notions of HDC as well
as flow of developing an HDC classifier. Instead, we make comparisons on both
the architecture and the learning process between a two-layer neural network
and the HDC model and show that an HDC model can be potentially derived from a
trained network as such.

##  III HDC versus NN: Architecture

###  III-A Item Memory vs. Input Layer

Figure 1: Architectural Comparison between HDC and neural network

We first formulate the item memory and the encoding process as the processing
of the input layer inside a neural network. As noted in Sec. II-B, the input
to the encoding phase is the sample and the output of is the HV with a
specific (pre-defined) dimensionality. This resembles the classical input
layer of a neural network that takes the samples then produce intermediate
layer outputs. The encoding is conventionally application or task dependent,
however the set of the HDC operations mostly features the three types of HDC
operations as introduced in Sec. II-A. Therefore, such a set can be
constructed by a combination of linear mappings, namely the forward pass of a
linear layer.

Without loss of generality, we assume the encoding process uses the commonly
used record-based encoding, as Eq. 9: the samples HV is obtained by adding up
the item HVs indexed from the item memory multiplied by the feature value.
This is actually a matrix multiplication between the input feature vector and
the item memory. Therefore, we can connect this to the linear layer of neural
network which can be described as Eq. 10, where $x$ and $y$ are the input and
output of the layer, and $W$ and $B$ are the weights and biases respectively.
From the perspective of HDC, the weights are essentially the item memory and
the biases are set to 0. If the encoding process features more HV operations
beyond multiplication, then biases can be used and multiple such layers can be
cascaded.

We can also find the counterpart of activation functions in neural networks in
HDC. After the encoding of input samples, HVs are often bipolarized or
binarized, where the numbers larger than 0 are set to 1 and numbers smaller
than 0 are set to -1 (or 0). Such bipolarization or binarization, similar to
the activation functions in neural networks, provide non-linearity to HDC so
that HDC models can be used to perform classification tasks, which is similar
to the kernel trick [4] in other machine learning algorithms such as support
vector machines. In this paper specifically, we apply hyperbolic tangent
activation (tanh) after the input layer of the neural network which has the
similar effect of bipolarization.

$\vec{V}=\sum_{m=1}^{M}{\mathbf{I}.index(f_{m})\times f_{m}}$ (9)

$y=W^{T}x+B$ (10)

###  III-B Associative Memory vs. Classifier Layer

We also formulate the associative memory as the classifier layer, i.e., the
output layer of a neural network. As introduced in Sec. II-B, the inference
process of HDC is the iterative similarity calculation between the query HV
and each class HV in the associative memory. Recall the definition of cosine
similarity at Eq. 4, we can ignore the $||\vec{V_{a}}||\times||\vec{V_{b}}||$
and simplify the calculation into the vector product. This further transforms
the inference process into another matrix multiplication and can subsequently
be regarded as a linear layer just like the classifier in a neural network.
The activation function after the classifier layer is softmax as it resembles
argmax in HDC inference which is used to locate the class with highest
similarity, but is differentiable.

##  IV HDC versus NN: Learning

We have already present the architectural comparison between an HDC model. To
make a further step, we also analyze in this subsection that the learning
process of HDC is also similar to the back-propagation. We address that three
critical characteristics of HDC learning process grant its advantages such as
energy efficiency, but on the other hand limit the potential of the learning
capability of high dimensional patterns for more complicated and difficult
datasets.

First, for the canonical HDC model, the item memory is usually fixed. From the
perspective of neural network, it means that only the classifier layer of the
formulated neural networks is trainable while the input layer is “freezed”.
The item memory will not be updated during the training and retraining
process. For neural network, it means the gradients are not back-propagated to
the input layer and will stop at the classifier layer, which is similar to
fine-tuning a retrained network model. Second, HDC training and retraining
also features a “coerce” version of back-propagation, which is different from
gradient descent: Unlike neural networks that the weights of each neuron can
be updated individually and freely, for HDC, the weights representing
associative memory can only be updated together, limited by the set of encoded
HVs available from the training set. We recognize such training is an
“approximate back-propagation” as the encoded HVs of each training sample
contribute to rather a limited vector space. Third, HDC learning rate is much
higher than that of neural networks. The canonical HDC training and retraining
uses a learning rate of 1, this explains why HDC training is much faster than
the neural networks as the accuracy could saturate after much less epochs.

##  V Experimental Results

In this section, based on the comparison and analysis we present above, we
show an experimental study that HDC model can be derived from a trained neural
network which can surpass accuracy of conventional HDC models. As presented in
Fig. 2, a two-layer neural network is trained using conventional neural
network training strategies. After training, the weights of each layer is
fetched and then duplicated as the item and associative memory during encoding
and inference.

###  V-A Experimental Setup

We use the MNIST dataset [11] as our benchmark dataset because it is one of
the datasets that HDC performs much less than state-of-the-art that most of
the HDC models can only achieve less than 95% accuracy [13]. We also use
CIFAR-10 dataset [10] which SOTA HDC can only achieve around 45% accuracy [3].

Figure 2: Derive an HDC model from a trained neural network.

We use a typical configuration of HDC with the dimensionality of 10,000. For
MNIST, we use the record-based encoding as introduced in Eq. 9, which
translates into a neural network model with two layers as specifies by Fig. 1.
For CIFAR-10, as the input image has three channels (R, G and B), therefore we
modify the record-based encoding as Eq. 11 so that each channel is encoded
separately like MNIST dataset. After encoding all the 3 channels, the HVs
representing each channel are added together each two so that different
channel information can be mixed together.

We also compare the performance with two baselines:

  * •

HDC-base: This baseline is the HDC model trained using the canonical (record-
based) encoding, training, and retraining process which can be found in the
majority of HDC related literature.

  * •

LeHDC: This baseline is implemented according to the learn-able HDC frameworks
proposed in [3].

$\displaystyle\vec{V_{RG}}=\vec{V_{R}}+\vec{V_{G}}$ (11)
$\displaystyle\vec{V_{RB}}=\vec{V_{R}}+\vec{V_{B}}$
$\displaystyle\vec{V_{GB}}=\vec{V_{G}}+\vec{V_{B}}$
$\displaystyle\vec{V}=\vec{V_{RG}}+\vec{V_{RB}}+\vec{V_{GB}}$

###  V-B Training of Neural Network

We implement the neural network using PyTorch framework, the HDC network
architecture can be concisely defined as a sequential model of PyTorch with
just a few lines along with the required activation functions. For example,
the code for defining HDC model for MNIST dataset is shown in Listing 1 as an
example. We train the neural network with Adam optimizer and use learning rate
0.001 and the training is terminated if inference accuracy does not
substantially increase after consecutive epochs.

⬇

1 def hdc(d_feature, d_HV, n_classes):

2 return nn.Sequential(

3 nn.Flatten(),

4 nn.Linear(d_feature, d_HV, bias = False),

5 nn.Tanh(),

6 nn.Linear(d_HV, n_classes, bias = False),

7 nn.Softmax(dim = 1))

Listing 1: Defining HDC Model for MNIST using PyTorch

###  V-C Derive an HDC from NN

We derive an HDC model from a trained network by extracting the weights of the
input and classifier layers. For the input layer, the size of the weight
matrix is $10000\times 768$, thus each column can be considered as an item HV
and the entire weight matrix, with a transpose, is thus the item memory. For
the classifier layer as the weight matrix size is $10\times 10000$, the row
instead can be considered as the class HV thus the weight matrix can be
considered as the associative memory.

We present an accuracy comparison of the two baseline models and the HDC model
transformed from the trained neural network in Table I. We can observe that
for the MNIST dataset, the HDC model derived from neural network can achieve
about 96.7% accuracy which surpasses the baseline by nearly 6% and the
learning based LeHDC by about 2%.

For the even more challenging CIFAR-10 dataset, the canonical HDC-base model
can only achieve unacceptable accuracy of 30%. For the LeHDC baseline, the
accuracy can increase to 46%. Although for this paper with HDC model
transformed from neural network, the accuracy is still only 51%, there is
already a 20% increase from the baseline.

As to computation cost, the HDC model transformed from the neural network
performs the same amount of computations as the HDC-Base during inference,
since they share the same architecture. The overhead is on the training
process since a neural network needs to be trained to obtain the parameters
such as weights to be transformed into the HDC memory elements. Additionally,
since the neural network architecture trained for transform is compact (as
shown in Listing 1 ), the training is also fast. With our experimental setup,
it takes around 4 and 7 minutes to achieve the reported accuracy even when
trained afresh.

TABLE I: Accuracy Comparison with Two Baseline Models | HDC-Base | LeHDC [3] | This Paper
---|---|---|---
MNIST | $90.93^{\pm 0.52}$ | $94.74^{\pm 0.18}$ | $96.71^{\pm 0.37}$
CIFAR-10 | $30.28^{\pm 1.90}$ | $46.10^{\pm 0.20}$ | $51.08^{\pm 0.79}$

###  V-D Discussion

HDC resembles the architecture of a extremely compact neural network with just
2 layers. Both the encoding of HV and the inference can be accomplished by a
typical fully connected layer. The item memory and the associative memory can
be transformed from the weights of a trained neural network in such an
architecture. The training of HDC models is also similar to the training of a
neural network. Instead of using back-propagation with gradient descent, HDC
use HV addition and subtraction to guide model to converge at the direction of
higher accuracy which is easier to implement. We recognize this as a
compromise to sacrifice some of the canonical neural network training schemes
for more energy efficiency and acceleration.

The learning capability of HDC is capped by the corresponding neural network
architecture. From the experimental results, although a two-layer neural
network can achieve acceptable accuracy on the MNIST, when the dataset becomes
much complicated and challenging like the CIFAR-10, such shallow network
structure cannot achieve an acceptable accuracy. This explains the reason that
the current HDC models mostly focus on simple applications or datasets and
cannot achieve comparable performance on more demanding learning tasks.

One major challenge of HDC is that the encoding process is not application-
agnostic. System designers are required to spend manual effort to design,
develop, and evaluate the encoding process, which can often lead to sub-par
results as there may exist undiscovered encoding methods with better
performance and also prohibits the scalability and flexibility. Neural network
has the advantage over HDC as the weights of neural network is individually
trainable, however, in HDC only the associative memory is trainable and the
elements inside each class HV is not individually trainable due to the
holographic representation of HVs.

##  VI Conclusion

The tremendously increasing popularity of Hyperdimensional Computing (HDC) has
attracted researchers from various domains to invest their effort in this
topic. The major advantages of HDC are better energy efficiency, smaller model
size, and acceleration on heterogeneous platforms. In this paper, we provide a
new perspective of getting insights of this emerging algorithm from the angle
of neural networks. Specifically, we present a comparative analysis and
experiment to illustrate the similarity between HDC and neural network on
architecture and learning process, and show that an HDC model can be derived
from a two-layer neural network. During experiments, we illustrate that by
training the neural network upfront and then derive an HDC model based on the
trained network, we can achieve up to 21% accuracy improvement from baseline
HDC models and up to 5% improvement from SOTA learning based HDC models.

## References

  * [1] Andrea Calimera.  Exploring Neural-symbolic Integration Architectures for Computer Vision.  PhD thesis, ETH Zurich, 2018.
  * [2] Cameron Diao, Denis Kleyko, Jan M Rabaey, and Bruno A Olshausen.  Generalized learning vector quantization for classification in randomized neural networks and hyperdimensional computing.  In 2021 International Joint Conference on Neural Networks (IJCNN), pages 1–9. IEEE, 2021.
  * [3] Shijin Duan, Yejia Liu, Shaolei Ren, and Xiaolin Xu.  Lehdc: Learning-based hyperdimensional computing classifier.  arXiv preprint arXiv:2203.09680, 2022.
  * [4] Martin Hofmann.  Support vector machines-kernels and the kernel trick.  Notes, 26(3):1–16, 2006.
  * [5] Mohsen Imani, Deqian Kong, Abbas Rahimi, and Tajana Rosing.  Voicehd: Hyperdimensional computing for efficient speech recognition.  In 2017 IEEE international conference on rebooting computing (ICRC), pages 1–8. IEEE, 2017.
  * [6] Pentti Kanerva.  Hyperdimensional computing: An introduction to computing in distributed representation with high-dimensional random vectors.  Cognitive computation, 1(2):139–159, 2009.
  * [7] Geethan Karunaratne, Manuel Le Gallo, Giovanni Cherubini, Luca Benini, Abbas Rahimi, and Abu Sebastian.  In-memory hyperdimensional computing.  Nature Electronics, 3(6):327–337, 2020.
  * [8] Yeseong Kim, Mohsen Imani, Niema Moshiri, and Tajana Rosing.  Geniehd: Efficient dna pattern matching accelerator using hyperdimensional computing.  In 2020 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 115–120. IEEE, 2020.
  * [9] Denis Kleyko, Dmitri A Rachkovskij, Evgeny Osipov, and Abbas Rahim.  A survey on hyperdimensional computing aka vector symbolic architectures, part ii: Applications, cognitive models, and challenges.  arXiv preprint arXiv:2112.15424, 2021.
  * [10] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * [11] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [12] Fangxin Liu, Haomin Li, Xiaokang Yang, and Li Jiang.  L3e-hd: A framework enabling efficient ensemble in high-dimensional space for language tasks.  In Proceedings of the 45th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 1844–1848, 2022.
  * [13] Dongning Ma, Jianmin Guo, Yu Jiang, and Xun Jiao.  Hdtest: Differential fuzz testing of brain-inspired hyperdimensional computing.  In 2021 58th ACM/IEEE Design Automation Conference (DAC), pages 391–396. IEEE, 2021.
  * [14] Dongning Ma, Rahul Thapa, and Xun Jiao.  Molehd: Drug discovery using brain-inspired hyperdimensional computing.  arXiv preprint arXiv:2106.02894, 2021.
  * [15] George Plastiras, Maria Terzi, Christos Kyrkou, and Theocharis Theocharidcs.  Edge intelligence: Challenges and opportunities of near-sensor machine learning applications.  In 2018 ieee 29th international conference on application-specific systems, architectures and processors (asap), pages 1–7. IEEE, 2018.
  * [16] Sahand Salamat, Mohsen Imani, Behnam Khaleghi, and Tajana Rosing.  F5-hd: Fast flexible fpga-based framework for refreshing hyperdimensional computing.  In Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, pages 53–62, 2019.
  * [17] Vivienne Sze, Yu-Hsin Chen, Tien-Ju Yang, and Joel S Emer.  Efficient processing of deep neural networks: A tutorial and survey.  Proceedings of the IEEE, 105(12):2295–2329, 2017.
  * [18] Rahul Thapa, Bikal Lamichhane, Dongning Ma, and Xun Jiao.  Spamhd: Memory-efficient text spam detection using brain-inspired hyperdimensional computing.  In 2021 IEEE Computer Society Annual Symposium on VLSI (ISVLSI), pages 84–89. IEEE, 2021.
  * [19] Anthony Thomas, Sanjoy Dasgupta, and Tajana Rosing.  Theoretical foundations of hyperdimensional computing.  arXiv preprint arXiv:2010.07426, 2020.
  * [20] Ruixuan Wang, Fanxin Kong, Hasshi Sudler, and Xun Jiao.  Brief industry paper: Hdad: Hyperdimensional computing-based anomaly detection for automotive sensor attacks.  In 2021 IEEE 27th Real-Time and Embedded Technology and Applications Symposium (RTAS), pages 461–464. IEEE, 2021.