# Quantum algorithms for charged particle track reconstruction in the LUXE
experiment

Arianna Crippa1,2 Lena Funcke3,4 Tobias Hartung5 Beate Heinemann6,7 Karl
Jansen1,8 Annabel Kropf6,7 Stefan Kühn1,8 Federico Meloni6 David Spataro6,7
Cenk Tüysüz1,2 and Yee Chinn Yap6 1 Deutsches Elektronen-Synchrotron DESY,
Platanenallee 6, 15738 Zeuthen, Germany  2 Institut für Physik, Humboldt-
Universität zu Berlin, Newtonstr. 15, 12489 Berlin, Germany  3
Transdisciplinary Research Area “Building Blocks of Matter and Fundamental
Interactions” (TRA Matter) and Helmholtz Institute for Radiation and Nuclear
Physics (HISKP), University of Bonn, Nußallee 14-16, 53115 Bonn, Germany  4
Center for Theoretical Physics, Co-Design Center for Quantum Advantage, and
NSF AI Institute for Artificial Intelligence and Fundamental Interactions,
Massachusetts Institute of Technology, 77 Massachusetts Avenue, Cambridge, MA
02139, USA  5 Northeastern University - London, Devon House, St Katharine
Docks, London, E1W 1LP, United Kingdom  6 Deutsches Elektronen-Synchrotron
DESY, Notkestr. 85, 22607 Hamburg, Germany  7 Physikalisches Institut, Albert-
Ludwigs-Universität Freiburg, Hermann-Herder-Str. 3a, 79104 Freiburg, Germany
8 Computation-Based Science and Technology Research Center, The Cyprus
Institute, 20 Kavafi Street, 2121 Nicosia, Cyprus<EMAIL_ADDRESS>
Preprint numbers: DESY-23-045 , MIT-CTP/5481

###### Abstract

The LUXE experiment is a new experiment in planning in Hamburg, which will
study Quantum Electrodynamics at the strong-field frontier. LUXE intends to
measure the positron production rate in this unprecedented regime by using,
among others, a silicon tracking detector. The large number of expected
positrons traversing the sensitive detector layers results in an extremely
challenging combinatorial problem, which can become computationally expensive
for classical computers. This paper investigates the potential future use of
gate-based quantum computers for pattern recognition in track reconstruction.
Approaches based on a quadratic unconstrained binary optimisation and a
quantum graph neural network are investigated in classical simulations of
quantum devices and compared with a classical track reconstruction algorithm.
In addition, a proof-of-principle study is performed using quantum hardware.

##  1 Introduction

The Laser Und XFEL Experiment (LUXE) [1] at DESY and the European XFEL
(Eu.XFEL) aims at studying strong-field Quantum Electrodynamics (QED)
processes in the interactions of a high-intensity optical laser and the 16.5
GeV electron beam of the Eu.XFEL ($e^{-}$-laser collisions), as well as with
high-energy secondary photons. A strong background field is provided by a
Terawatt-scale laser pulse and enhanced by the Lorentz boost of the electrons,
allowing LUXE to explore a previously uncharted intensity regime.

In this regime, one of the main goals of the LUXE experiment is to measure the
positron rate as a function of the laser intensity parameter $\xi$, defined as

$\xi=\sqrt{4\pi\alpha}\,\,\frac{\epsilon_{L}}{\omega_{L}m_{e}}=\frac{m_{e}\epsilon_{L}}{\omega_{L}\epsilon_{cr}},$
(1)

where $\alpha$ is the fine structure constant, $\epsilon_{L}$ is the laser
field strength, $\omega_{L}$ is the frequency of the laser, $m_{e}$ is the
electron mass, and $\epsilon_{cr}=1.32\times 10^{18}$ V/m is the critical
field strength, also known as the Schwinger limit [2]. The measured positron
rate will be compared to theoretical predictions. When considering electron-
laser collisions, the dominant process is the non-linear Compton scattering
[3, 4]. In non-linear Compton scattering, the incident electron absorbs
multiple laser photons, emitting a Compton photon, which can then interact
again with the laser field to produce electron-positron pairs [5, 6, 7]. The
expected number of positrons per bunch crossing (BX) as a function of $\xi$
spans over five orders of magnitude in the range shown in Figure 1.

Figure 1: Number of positrons per bunch crossing produced in $e^{-}$-laser
collisions as a function of the laser field intensity parameter $\xi$, for
different values of the laser power. Based on Ref. [1], with additional
simulated events.

The measurement of the positron rate will be performed by a dedicated set of
detectors comprising a silicon pixel tracker and a calorimeter. The wide range
of expected positron rates poses a significant challenge to event
reconstruction, especially within the tracker, where the large number of
energy deposits could lead to finding spurious tracks that do not correspond
to a real particle. The most relevant tracking challenge for this work is to
maintain a linear dependence of the number of reconstructed tracks as a
function of the number of charged particles in the event up to very high
particle multiplicities.

This work investigates the potential future use of gate-based quantum
computers for pattern recognition in track reconstruction and compares the
obtained performance to classical methods. Analogous studies have focused on
track reconstruction in the proton-proton collision environments of the Large
Hadron Collider and its upgrades, by using quantum annealers [8, 9], quantum
associative memories [10] or quantum graph neural networks [11]. A review of
various quantum computing algorithms studied for charged particle tracking can
be found in Ref. [12]. In this work, we present an update of our previous
study of track reconstruction with quantum algorithms at LUXE [13, 14].

This paper is organised as follows. A brief characterisation of the current
proposed detector layout and the data-taking environment are given in Section
2. The data sets used in this study are presented in Section 3, together with
the dedicated simulation software. Section 4 presents the methodology used for
the reconstruction of the simulated data. The results are discussed in Section
5, focusing first on classical simulations of quantum hardware and then
presenting a set of studies performed on quantum hardware (ibm_nairobi). The
summary and conclusion are given in Section 6, while an outlook on future
developments and work is discussed in Section 7.

##  2 The LUXE experiment

This work focuses on the reconstruction of the electron-laser collisions. In
this setup, the electron beam from the Eu.XFEL is guided to the interaction
point (IP), where it collides with a laser beam. The experiment plans to start
taking data with a 40 TW laser, which will later be upgraded to reach 350 TW.
The electrons and positrons produced in the electron-laser interactions are
deflected by a 0.95 T dipole magnet and then detected by a positron detection
system, as shown in Figure 2. 111LUXE uses a right-handed coordinate system
with its origin at the nominal interaction point and the $z$-axis along the
beam line. The $y$-axis points upwards, and the $x$-axis points towards the
positron detection system.

Figure 2: Schematic layout of the positron detection system in LUXE for the
electron-laser setup. Adapted from Ref. [1]. The angle $\theta$ represents the
crossing angle of the Eu.XFEL and laser beams.

The outgoing positrons are detected using a silicon pixel tracking detector.
The tracker consists of four layers, each comprising two $\approx 27$ cm long
staves placed next to each other, which overlap partially, as illustrated in
the figure. The layers are spaced 10 cm away from each other along the beam
axis. The average thickness of the staves is $0.357\%$ of a radiation length.
Each stave contains nine sensors, composed of $512\times 1024$ pixels of size
$27\times 29~{}{\mu\textrm{m}}^{2}$. The pixel sensors have a detection
efficiency above 99%, a noise hit rate much below $10^{-5}$ and a spatial
resolution of around $5~{}\mu$m.

##  3 Simulated data

Monte Carlo simulated event samples are used to perform this study. The
calculation for the electron-laser interaction processes was performed with
the PTARMIGAN [15] Monte Carlo event generation software. The electron beam
parameters were chosen as follows. The incoming electron energy
$\varepsilon_{e}$ is set to $16.5$ GeV, the beam spot size to
$\sigma_{x}=\sigma_{y}=5~{}\mu$m, $\sigma_{z}=24~{}\mu$m, and the normalised
emittance to $1.4$ mm$\cdot$mrad. The simulation of the laser assumes a 40 TW
laser, an energy after compression of 1.2 J and a pulse length of 30 fs. The
laser pulse is modelled as having a Gaussian profile both in the longitudinal
and in the transverse direction. The laser spot waist, which for a Gaussian
pulse corresponds to $2\sigma$ in intensity, decreases with $\xi$ and varies
between 6 $\mu$m and 3 $\mu$m.

The particles produced in the electron-laser interactions are propagated
through the dipole magnet and tracking detector using a custom fast simulation
that was developed for this study. The fast simulation uses parameterised
smearing functions to model the effects of multiple scattering and detector
resolution. Furthermore, a simplified detector layout is considered. In this
layout, the four detection layers are not split into two overlapping staves,
but simply have a double length with no discontinuities.

To perform these studies, data sets corresponding to electron-laser
interactions were generated with $\xi$ values ranging from three to seven and
a laser power of 40 TW. This corresponds to positron multiplicities ranging
between $1\times 10^{2}$ and $7\times 10^{4}$. Figure 3 shows the resulting
expected positron energy distribution for the three generated $\xi$ values
(left) and the number of hits/mm2 in the first detector layer as a function of
the $x$ and $y$ coordinates for $\xi=7$ (right). The double-peaked structure
visible in the $xy$ plane reflects the initial positron momentum distribution
along the $y$-axis at the interaction point.

Figure 3: Left: Positron energy distribution for different values of $\xi$,
normalised to unit area. Based on Ref. [1], using the data sets generated for
this work. Right: Number of hits/mm2 in the first detector layer as a function
of the $x$ and $y$ coordinates for $\xi=7$.

##  4 Methodology

The starting point for the pattern recognition are either doublets or
triplets, defined as a set of two or three hits in consecutive detector
layers. A pre-selection is applied to the initial doublet or triplet
candidates to reduce the combinatorial candidates while keeping the efficiency
as close as possible to 100% for the doublets and triplets matching with a
real positron. Doublets are formed first and are required to satisfy a pre-
selection based on the ratio $\delta x/x_{0}$, where $\delta x$ is the
difference of the $x$ coordinates for the two hits composing the doublet,
while $x_{0}$ indicates the $x$ coordinate on the detector layer closest to
the interaction point. A window of three standard deviations around the
expected mean value of $\delta x/x_{0}$ for true doublets, as determined in
the simulation, is used for this selection. This requirement ensures that the
particles come from the IP. Triplets are subsequently constructed by combining
doublet candidates with a requirement on the maximum angle difference
$\delta\theta=\sqrt{\delta\theta_{xz}^{2}+\delta\theta_{yz}^{2}}$ of the
doublet pairs. The maximum scattering threshold is chosen to be 1 mrad and was
optimised taking into account multiple scattering with the detector material.
Since triplets consist of three hits, they are formed either from the first to
the third layer or from the second to the fourth layer.

Figure 4 shows the distributions of $\delta x/x_{0}$ for doublets (left) and
$\delta\theta$ for pairs of doublets (right) originating from true positron
tracks, shown separately for low-energy ($E_{e^{+}}<3$ GeV) and high-energy
positrons ($E_{e^{+}}>3$ GeV), as well as the chosen thresholds. The
distributions are obtained using $\xi=7$, but are generally $\xi$-independent.
The $\delta x/x_{0}$ distribution shows a slight dependence on positron
energy, while the triplet $\delta\theta$ distribution demonstrates that the
scattering is more pronounced for lower energy positrons. The resulting pre-
selection efficiencies are shown in Figure 5 (left) for both doublet and
triplet finding, in the case of electron-laser interaction for $\xi=7$. The
pre-selection requirements are found to be nearly fully efficient for the
whole energy range, with a moderate efficiency loss, at the level of 16% for
positron energies below 2 GeV, mostly due to multiple scattering with the
detector material. Figure 5 (right) also shows the number of doublets and
triplets passing the pre-selection criteria as a function of $\xi$.

Figure 4: Left: Distribution of doublet $\delta x/x_{0}$ with red dashed lines
indicating the range of the pre-selection. Right: Distribution of angle
difference $\delta\theta$ for the doublet pairs composing the triplets with a
red dashed line indicating the upper limit allowed by the pre-selection.

Figure 5: Left: Doublet and triplet-finding efficiency as a function of the
positron true energy. The combined efficiency is also shown. Right: Doublet
and triplet multiplicities as a function of $\xi$ (lower $x$-axis),
corresponding to the average number of positrons (upper $x$-axis).

Three pattern recognition methods are employed and systematically compared to
reconstruct tracks from the detector hits. The first method formulates the
tracking problem as a quadratic unconstrained binary optimisation (QUBO),
similar to the one used in Ref. [8], which is then processed with quantum
algorithms. The second method uses a hybrid quantum-classical graph neural
network approach [11], but is limited to specific scenarios compatible with
the available devices. Finally, the results obtained with the quantum
approaches are compared to an optimised classical approach based on a Kalman
filter [16, 17], which is taken to be the reference for the state-of-the-art
using no quantum computers.

###  4.1 Quadratic unconstrained binary optimisation

In this approach, the pairs of triplet candidates that can be combined to form
tracks are identified by solving a QUBO problem. The QUBO is expressed via the
objective function

$O=\sum_{i}^{N}\sum_{j<i}b_{ij}T_{i}T_{j}+\sum_{i=1}^{N}a_{i}T_{i},$ (2)

where $T_{i}$ and $T_{j}$ are triplets of hits and $a_{i}$ and $b_{ij}$ are
real coefficients. The triplets $T_{i}$ and $T_{j}$ assume binary values. The
solution of the QUBO determines whether each triplet is considered false and
rejected, by being set to zero, or true and selected, by being set to one. The
linear term of the QUBO weighs the individual triplets by their quality
quantified by the coefficient $a_{i}$. The $a_{i}$ coefficient is set to the
value of $\delta\theta$ scaled to populate the $[-1;1]$ range. The quadratic
term represents the interactions between triplet pairs, where the coefficient
$b_{ij}$ characterises their compatibility. The coefficient $b_{ij}$ is
computed from the doublets forming the two considered triplets. It is taken to
be the norm of the sum of the standard deviations of the doublet angles in the
$xy$ and $yz$ planes, translated and scaled to populate the $[-1;-0.9]$ range.
If the two triplets are in conflict, the coefficient $b_{ij}$ is set to one.
If the triplets are not connected, it is set to zero.

The QUBO in Eq. (2) can be mapped to an Ising Hamiltonian by mapping
$T_{i}\rightarrow(1+Z_{i})/2$, where $Z_{i}$ is the third Pauli matrix.
Minimising the QUBO is equivalent to finding the ground state of the
Hamiltonian. The Variational Quantum Eigensolver (VQE) [18] method, a hybrid
quantum-classical algorithm, was used to find the ground state. In this work,
the data is processed using the VQE implementation available in the Qiskit
[19] library. Most results rely on classical simulations of quantum circuits,
where no sources of noise or decoherence are included, and a simple ansatz
with $R_{Y}$ gates and a linear CNOT entangler is chosen, as shown in Figure
4.1. An ansatz with CNOTs between all possible pairs and a single circuit
repetition was found to lead to results compatible within statistical
uncertainties, but was discarded for simplicity. The selected optimiser is the
Nakanishi-Fujii-Todo (NFT) [20] algorithm. The ansatz and optimiser were
selected as those leading to the highest track reconstruction efficiency in
previous work [14].

Figure 6: Layout of the variational quantum circuit using the ansatz with
$R_{Y}$ gates and a linear CNOT entangling pattern. For simplicity, only four
qubits are shown.

The number of qubits required to represent the tracking problem as a QUBO is
determined by the number of triplet candidates. Due to the limited number of
qubits available on the current quantum devices, the QUBO in this work is
partitioned into QUBOs of smaller size (referred to as sub-QUBOs) to be solved
iteratively. For small enough sub-QUBO sizes, such as the size 7 used in this
work, an exact solution using matrix diagonalisation is possible and is used
as a benchmark.

Figure 7 summarises the QUBO solving process. At the beginning of the
processing, all triplet candidates are set to 1. The splitting into sub-QUBOs
is done by extracting the sub-QUBO matrices of the desired size, by picking
triplets in order of their impact. The impact is defined as the change in the
value of the objective function when $T_{i}\rightarrow 1-T_{i}$. Each triplet
is assigned an additional constant term representing the sum of all
interactions with triplets outside of the sub-QUBO to retain sensitivity to
the connections outside of each sub-QUBO when computing the value of the
objective function. After the sub-QUBOs are solved, the solution is combined.
These steps are repeated for a number of iterations. The triplets selected by
the QUBO minimisation are retained and matched to form track candidates.

Figure 7: Diagram illustrating the QUBO solving procedure.

Alternative algorithms for finding the optimal QUBO solution, such as the
Quantum Approximate Optimisation Algorithm (QAOA) [21], were briefly
investigated and were found to lead to significantly worse performance. A
dedicated optimisation and characterisation of the results of such alternative
algorithms is left to future work.

###  4.2 Quantum graph neural network

This approach is based on a graph neural network (GNN) [22, 23] that consists
of both classical neural network layers and quantum circuits. The graph is
constructed from doublets, where the hits are nodes and the connections
between the hits are edges. All nodes of consecutive layers are connected and
only the ones that satisfy the pre-selection criteria are kept. The quantum
graph neural network (QGNN) model follows the implementation of Ref. [11] and
consists of three networks. First, the InputNet takes the input node features,
i.e. the three spatial coordinates, and produces hidden node features. For
this purpose, a single fully connected neural network layer that has 10
neurons with a tanh activation function is used. Second, the EdgeNet takes all
connected node pairs as input and produces a scalar edge feature for each of
them using a sigmoid activation function. This will later be the prediction
score of the model for each doublet, as this model is essentially a segment
classifier. Circuit 10 with two layers and 10 qubits is selected for this task
based on previous work [11]. Each layer of this circuit uses $R_{Y}$ gates and
linear CNOT entanglers between all possible pairs of qubits. Third, the
NodeNet considers each node and its connecting nodes to update the hidden node
features. The architecture of the NodeNet is similar to EdgeNet, but it uses
the tanh activation function for the last layer, as the NodeNet is an
intermediate step, and sigmoid activation functions are known to lead to
vanishing gradients.

The quantum graph neural network (QGNN) model first starts with the InputNet.
Then, the EdgeNet and the NodeNet are applied alternately four times to allow
the node features to be updated using farther nodes, as determined in a scan
of the optimal model parameters. At the end, the EdgeNet is applied one last
time to obtain the predictions for each doublet connection. Finally, the edges
are discarded if the prediction value is less than a fixed threshold (chosen
to be 0.5 in our simulations) and the rest are retained and used to form track
candidates.

###  4.3 Combinatorial Kalman filter

A tracking algorithm based on A Common Tracking Software (ACTS) toolkit [24]
with the combinatorial Kalman Filter (CKF) technique for track finding and
fitting is used as a benchmark. In this classical tracking method, track
finding starts from seeds, which are the triplets formed from the first three
detector layers. To avoid a combinatorial growth in the number of seeds at
high particle density, further constraints are placed on seeds sharing the
same hits by prioritising the better-aligned seeds. An initial estimate of
track parameters is obtained from the seed and is used to predict the next hit
and is updated progressively, with the measurement search performed at the
same time as the fit.

###  4.4 Final track selection

A final step in the track reconstruction is common to all considered methods.
Track candidates are required to have four hits and, as explained in the
previous subsections, can be found with the QUBO approach that combines
triplets into quadruplets (see Section 4.1), by employing the QGNN approach
that combines doublets into quadruplets (see Section 4.2), or by using the
classical CKF method (see Section 4.3). After finding these track candidates,
the final tracks now have to be selected among these candidates, using a final
step explained in the following.

The track candidates are fitted to straight lines with the least-square
method, as the particles propagate through the tracking detector in absence of
a magnetic field. A track candidate is considered matched if it has at least
three out of four hits matched to the same particle. Figure 8 (left) shows the
duplication rate, i.e. the fraction of matched particles that are matched to
more than one track candidate, as a function of $\xi$. The substantially
larger duplication rate of the CKF technique is due to this method being a
local approach with no knowledge of the overall BX, unlike the QUBO and QGNN-
based approaches.

Figure 8: Left: Duplication rate as a function of $\xi$. The results from the
exact matrix diagonalisation are shown as a line to help the comparison
between the methods. The results based on hybrid quantum-classical methods
rely on classical simulations of quantum devices. The decrease in duplication
rate for CKF for $\xi>5$ is due to the limit set on seeds with shared hits and
an overall decrease in tracking efficiency in this scenario. See Figure 5
(right) for the number of positrons corresponding to each $\xi$. Right:
Distribution of the $\chi^{2}$ divided by the number of degrees of freedom for
fitted track candidates found using the QUBO approach with exact matrix
diagonalisation, shown separately for matched (blue) and fake (red) track
candidates. The dashed lines represent the track candidates from the QUBO
solution, while the solid lines represent the selected tracks after the
resolution of reconstruction ambiguities.

To resolve the overlaps between the track candidates and to reject fake
tracks, an ambiguity resolution step is performed. The track candidates are
scored based on the $\chi^{2}$/ndf of the track fit and the number of shared
hits with other track candidates. The track candidates with the most shared
hits are evaluated first. They are compared to the other track candidates
sharing the same hits, and the ones with worse $\chi^{2}$/ndf of the track fit
are rejected. The procedure is repeated until all remaining tracks have up to
one shared hit. Figure 8 (right) shows the effect of the ambiguity resolution
on matched and fake tracks for a QUBO solved using matrix diagonalisation in a
BX with $\xi=7$. This scenario was selected to show the effect for the highest
particle multiplicity considered in this work.

##  5 Results

###  5.1 Studies with classical hardware

The results presented in the following are obtained on classical hardware,
including classical simulations of quantum hardware. A set of studies
performed on quantum hardware (ibm_nairobi) will be presented in Section 5.2.
The performance of various tracking methods is assessed using the efficiency
and the fake rate as metrics, which are computed on the final set of tracks.
The efficiency and fake rate are defined as

$\textrm{Efficiency}=\frac{N_{\rm tracks}^{\rm matched}}{N_{\rm tracks}^{\rm
generated}}\qquad\text{and}\qquad\textrm{Fake rate}=\frac{N_{\rm tracks}^{\rm
fake}}{N_{\rm tracks}^{\rm reconstructed}}\,.$ (3)

Figure 9 shows the average track reconstruction efficiency (left) and fake
rate (right) as a function of the laser field intensity parameter $\xi$ for
all tested approaches: QUBO-based tracking (both with the approximate solution
obtained with VQE and the exact solution via matrix diagonalisation), QGNN-
based tracking, and conventional CKF-based tracking.

Figure 9: Left: Track reconstruction efficiency as a function of the field
intensity parameter $\xi$. Right: Track fake rate as a function of $\xi$. The
results from the exact matrix diagonalisation are shown as a line to help the
comparison between the methods. The empty triangles show the results of a QGNN
training limited to 90 BXs. See Figure 5 (right) for the number of positrons
corresponding to each $\xi$. The results based on hybrid quantum-classical
methods rely on classical simulations of quantum devices.

The performance of CKF-based tracking is used as a state-of-the-art benchmark.
The excellent performance of the classical method deteriorates with $\xi$,
because of the increasing hit density. The results using the exact matrix
diagonalisation to solve the QUBO are well aligned with the CKF algorithm and
achieve a higher efficiency by 1–2% for large values of $\xi$ at the cost of
an increase in the fake rate of approximately a factor of two. The rate of
purely combinatorial tracks, i.e. tracks reconstructed from four hits
belonging to four distinct positrons, accounts for about 50% of the total fake
rate, independently of the reconstruction algorithm considered. The results
for VQE are in excellent agreement, within the statistical uncertainties, with
those from the matrix diagonalisation.

The results for the QGNN-based tracking are shown up to $\xi=4$, above which
simulating the quantum circuits becomes computationally prohibitive with the
currently available resources. The reconstruction efficiency is found to be
compatible with the other methods, with a substantially higher fake rate.
Further work aimed at optimising the selection of the EdgeNet predictions
could mitigate this effect. The QGNN results were validated by implementing a
classical GNN [22, 23] with the same architecture, but with 128 node hidden
features, finding excellent agreement. For $\xi=3$, two values of QGNN
efficiency are shown. The empty triangle is the result based on 100 BXs, i.e.
the same number of BX used to evaluate the performance of the CKF and QUBO-
based methods, using 90% of the data for the training of the model and 10% for
the inference. Because of the modest particle multiplicity expected at
$\xi=3$, the number of true tracks used in the QGNN training is too small to
obtain an optimal result. The full triangles show the efficiency obtained with
the QGNN training based on data generated with $\xi=4$, which corresponds to a
substantially larger set of true tracks, restoring a higher efficiency.

Figure 10: Track reconstruction efficiency as a function of the number of true
tracks used in the training of a classical GNN (green squares) and the QGNN
(brown triangles) for $e^{-}$-laser collisions with $\xi=3$. The QGNN results
rely on classical simulations of quantum hardware.

The dependency of the track reconstruction efficiency on the GNN-based
approaches was further studied in $e^{-}$-laser collisions with $\xi=3$,
comparing the results obtained with the QGNN and with a classical GNN for
different numbers of true tracks used in the training. The findings are
presented in Figure 10. The efficiency results for the largest track
multiplicity of both GNNs are obtained performing the training on events with
a larger value of $\xi=5$ for the classical GNN and $\xi=4$ for the QGNN. All
other data points are obtained by increasing the number of BXs considered at
$\xi=3$. While it is not expected for the QGNN and the classical GNN to
perfectly overlap in performance because of the slightly different model
architectures, the results show compatible trends when considering additional
data for a fixed value of $\xi$ and using models trained on BXs with larger
$\xi$.

Figure 11 shows the track reconstruction efficiency (left) and fake rate
(right) as a function of the true positron energy for the case of $\xi=5$, for
the CKF and QUBO-based methods. The methods show similar behaviours, with a
decrease in the region corresponding the highest detector occupancy. Because
of effects coming from the propagation through the magnetic field and from the
longitudinal size of the interaction region, the maximum occupancy shown in
Figure 3, does not correspond to the maximum of the positron energy
distribution. The reduced efficiency of the QUBO-based methods for positrons
with an energy below 3 GeV is dominated by the pre-selection efficiency shown
in Figure 5 (left).

The average energy resolution of the reconstructed tracks was also compared
between the different methods. The track energy resolution was found to be
0.5% and independent of the reconstruction method within the statistical
uncertainty of the analysed data set.

Figure 11: Left: Track reconstruction efficiency as a function of the positron
true energy for $\xi=5$. Right: Track fake rate as a function of the measured
track energy for $\xi=5$. The results based on hybrid quantum-classical
methods rely on classical simulations of quantum devices. On average, about
10500 positrons are expected to be produced in a BX with $\xi=5$.

###  5.2 Studies with quantum hardware

This section presents a detailed assessment of the performance of the VQE
algorithm on QUBOs of size seven, chosen to be the same as the sub-QUBO size
used for the results based on classically simulated VQE in Section 5.

A QUBO representing two nearby particles, leading to a total of seven
triplets, was selected for this test. The VQE method was applied first in an
exact classical simulation assuming an ideal quantum device with shot noise
only, then in a classical simulation involving a noise model extracted from a
snapshot of the measured noise of the ibm_nairobi device (fake_nairobi) and
finally using real quantum hardware (ibm_nairobi).

For each of these scenarios, 512 circuit evaluations (shots) were considered.
When performing the computations with fake_nairobi and ibm_nairobi, a
measurement error mitigation based on the generation of a calibration matrix
was used [25, 26]. The readout error probabilities were calibrated every 30
function evaluations of the optimiser.

Figure 12 shows the probabilities of the returned results for these three
scenarios, where the correct binary solution 0001111 is also the most
probable.

Figure 12: Distribution of the VQE results for a test QUBO composed of seven
triplets. The blue bars indicate the results obtained from 512 shots on the
ibm_nairobi quantum computer, compared with a realistic (green bars) and an
ideal (blue bars) classical simulation of the same system. The results from
the realistic classical simulation and from ibm_nairobi use a measurement
error mitigation technique based on the generation of a calibration matrix
[25, 26].

##  6 Conclusion

This work investigated the use of hybrid quantum-classical algorithms for
particle track reconstruction. Focusing on a VQE approach for a QUBO
formulation of track reconstruction and a QGNN approach, the performance of
these hybrid quantum-classical methods was compared to results obtained from a
state-of-the-art classical tracking method.

In order to produce these results, a standalone fast simulation of the LUXE
tracking detector was put in place as well as a software framework to
reconstruct tracks up to the maximum number of positrons expected during the
data taking with a laser power of 40 TW.

The results were analysed in terms of reconstruction efficiency, fake rate and
energy resolution. Hybrid quantum-classical algorithms were found to lead to
competitive results when compared to classical algorithms. For large particle
multiplicities, a QUBO approach based on VQE using a classical simulation of a
quantum device was found to have moderately higher efficiency than classical
tracking, but with a significant increase in the fake rate. It was not
possible, due to limitations in the computing resources, to evaluate the
performance of the approach based on QGNNs beyond a few thousand charged
particles.

##  7 Outlook

In this work, it was observed that the impact-based processing order leads to
a significant fraction of trivially-solvable sub-QUBOs with no interacting
triplets. Future work will be aimed at developing alternative algorithms for
the sorting of the binary vector representing the triplet candidates and for
the splitting of the problem into sub-QUBOs. To further reduce the computation
time and the rate of fake tracks reconstructed with this method, future work
will focus on optimising the scaling ranges for the $a_{i}$ and $b_{ij}$
coefficients.

While the initial study of the VQE performance on real quantum hardware
(ibm_nairobi) yielded promising results, a more systematic study of hybrid
quantum-classical algorithms using NISQ-era devices will be performed in
future work.

Finally, the choice of the optimiser used for VQE has a significant impact on
the probability to find the true minimum of the cost function, and a careful
optimisation will be required when considering larger sub-QUBO sizes.

The authors thank the LUXE collaboration for fostering this work. The work by
B.H., A.K., F.M., D.S. and Y.Y. were in part funded by the Helmholtz
Association - “Innopool Project LUXE-QED”. A.C., K.J. and C.T. are supported
in part by the Helmholtz Association - “Innopool Project Variational Quantum
Computer Simulations (VQCS)”. L.F. is partially supported by the U.S.
Department of Energy, Office of Science, National Quantum Information Science
Research Centers, Co-design Center for Quantum Advantage (C2QA) under contract
number DE-SC0012704, by the DOE QuantiSED Consortium under subcontract number
675352, by the National Science Foundation under Cooperative Agreement
PHY-2019786 (The NSF AI Institute for Artificial Intelligence and Fundamental
Interactions, http://iaifi.org/), and by the U.S. Department of Energy, Office
of Science, Office of Nuclear Physics under grant contract numbers DE-
SC0011090 and DE-SC0021006. S.K. acknowledges financial support from the
Cyprus Research and Innovation Foundation under project “Future-proofing
Scientific Applications for the Supercomputers of Tomorrow (FAST)”, contract
no. COMPLEMENTARY/0916/0048. This work is supported with funds from the
Ministry of Science, Research and Culture of the State of Brandenburg within
the Centre for Quantum Technologies and Applications (CQTA). This work is
funded within the framework of QUEST by the European Union’s Horizon Europe
Framework Programme (HORIZON) under the ERA Chair scheme with grant agreement
No. 101087126. This work has benefited from computing services provided by the
German National Analysis Facility (NAF).

## References

## References

  * [1] H. Abramowicz et al., Conceptual design report for the LUXE experiment, Eur. Phys. J. ST 230 (2021) no. 11, 2445–2560, arXiv:2102.02032 [hep-ex].
  * [2] J. S. Schwinger, On gauge invariance and vacuum polarization, Phys. Rev. 82 (1951) 664–679.
  * [3] A. I. Nikishov and V. I. Ritus, Quantum Processes in the Field of a Plane Electromagnetic Wave and in a Constant Field 1, Sov. Phys. JETP 19 (1964) 529–541.
  * [4] L. S. Brown and T. W. B. Kibble, Interaction of Intense Laser Beams with Electrons, Phys. Rev. 133 (1964) A705–A719.
  * [5] G. Breit and J. A. Wheeler, Collision of two light quanta, Phys. Rev. 46 (1934) no. 12, 1087–1091.
  * [6] H. R. Reiss, Absorption of Light by Light, J. Math. Phys. 3 (1962) 59.
  * [7] N. B. Narozhnyĭ, Propagation of plane electromagnetic waves in a constant field, Sov. Phys. JETP 28 (1969) 371–374.
  * [8] F. Bapst, W. Bhimji, P. Calafiura, H. Gray, W. Lavrijsen, L. Linder, and A. Smith, A pattern recognition algorithm for quantum annealers, Comput. Softw. Big Sci. 4 (2020) no. 1, 1, arXiv:1902.08324 [quant-ph].
  * [9] T. Schwägerl, C. Issever, K. Jansen, T. J. Khoo, S. Kühn, C. Tüysüz, and H. Weber, Particle track reconstruction with noisy intermediate-scale quantum computers, arXiv:2303.13249 [quant-ph].
  * [10] I. Shapoval and P. Calafiura, Quantum Associative Memory in HEP Track Pattern Recognition, EPJ Web Conf. 214 (2019) 01012, arXiv:1902.00498 [hep-ex].
  * [11] C. Tüysüz, C. Rieger, K. Novotny, B. Demirköz, D. Dobos, K. Potamianos, S. Vallecorsa, J.-R. Vlimant, and R. Forster, Hybrid Quantum Classical Graph Neural Networks for Particle Track Reconstruction, Quantum Machine Intelligence 3 (2021) 29, arXiv:2109.12636 [quant-ph].
  * [12] H. M. Gray, Quantum pattern recognition algorithms for charged particle tracking, Phil. Trans. Roy. Soc. Lond. A 380 (2021) no. 2216, 20210103.
  * [13] L. Funcke, T. Hartung, B. Heinemann, K. Jansen, A. Kropf, S. Kühn, F. Meloni, D. Spataro, C. Tüysüz, and Y. C. Yap, Studying quantum algorithms for particle track reconstruction in the LUXE experiment, J. Phys. Conf. Ser. 2438 (2023) no. 1, 012127, arXiv:2202.06874 [hep-ex].
  * [14] A. Crippa, L. Funcke, T. Hartung, B. Heinemann, K. Jansen, A. Kropf, S. Kühn, F. Meloni, D. Spataro, C. Tüysüz, and Y. C. Yap, Track reconstruction at the LUXE experiment using quantum algorithms,  10, 2022.  arXiv:2210.13021 [hep-ex].
  * [15] T. G. Blackburn, A. J. MacLeod, and B. King, From local to nonlocal: higher fidelity simulations of photon emission in intense laser pulses, New J. Phys. 23 (2021) no. 8, 085008, arXiv:2103.06673 [hep-ph].
  * [16] R. E. Kalman, A New Approach to Linear Filtering and Prediction Problems, Journal of Basic Engineering 82 (1960) no. 1, 35–45.
  * [17] P. Billoir, Track Fitting With Multiple Scattering: A New Method, Nucl. Instrum. Meth. A 225 (1984) 352–366.
  * [18] A. Peruzzo, J. McClean, P. Shadbolt, M.-H. Yung, X.-Q. Zhou, P. J. Love, A. Aspuru-Guzik, and J. L. O’Brien, A variational eigenvalue solver on a photonic quantum processor, Nat. Commun. 5 (2014) 1.
  * [19] M. Treinish, J. Gambetta, S. Thomas, P. Nation, qiskit bot, P. Kassebaum, D. M. Rodríguez, S. de la Puente González, J. Lishman, S. Hu, L. Bello, J. Garrison, K. Krsulich, J. Huang, J. Yu, M. Marques, E. Arellano, J. Gacon, D. McKay, J. Gomez, L. Capelluto, Travis-S-IBM, A. Mitchell, A. Panigrahi, lerongil, R. I. Rahman, S. Wood, T. Itoko, A. Pozas-Kerstjens, and C. J. Wood, Qiskit/qiskit: Qiskit 0.42.1, Mar., 2023.  https://doi.org/10.5281/zenodo.7757946.
  * [20] K. M. Nakanishi, K. Fujii, and S. Todo, Sequential minimal optimization for quantum-classical hybrid algorithms, Phys. Rev. Res. 2 (2020) 043158.
  * [21] E. Farhi, J. Goldstone, and S. Gutmann, A Quantum Approximate Optimization Algorithm, arXiv:1411.4028 (2014) .
  * [22] S. Farrell et al., Novel deep learning methods for track reconstruction, in 4th International Workshop Connecting The Dots 2018.  10, 2018.  arXiv:1810.06111 [hep-ex].
  * [23] X. Ju et al., Performance of a geometric deep learning pipeline for HL-LHC particle tracking, Eur. Phys. J. C 81 (2021) no. 10, 876, arXiv:2103.06995 [physics.data-an].
  * [24] X. Ai et al., A Common Tracking Software Project, Comput. Softw. Big Sci. 6 (2022) no. 1, 8, arXiv:2106.13593 [physics.ins-det].
  * [25] S. Bravyi, S. Sheldon, A. Kandala, D. C. Mckay, and J. M. Gambetta, Mitigating measurement errors in multiqubit experiments, Physical Review A 103 (2021) no. 4, 042605, arXiv:2006.14044 [quant-ph].
  * [26] N. Acharya and S. M. Saeed, A Lightweight Approach to Detect Malicious/Unexpected Changes in the Error Rates of NISQ Computers,  in Proceedings of the 39th International Conference on Computer-Aided Design, ICCAD ’20.  Association for Computing Machinery, New York, NY, USA, 2020.


# Negative votes to depolarize politics

Karthik H. Shankar  Email<EMAIL_ADDRESS>Center for Memory and Brain,
Boston University

###### Abstract

The controversies around the 2020 US presidential elections certainly casts
serious concerns on the efficiency of the current voting system in
representing the people’s will. Is the naive Plurality voting suitable in an
extremely polarized political environment? Alternate voting schemes are
gradually gaining public support, wherein the voters rank their choices
instead of just voting for their first preference. However they do not capture
certain crucial aspects of voter preferences like disapprovals and
negativities against candidates. I argue that these unexpressed negativities
are the predominant source of polarization in politics. I propose a voting
scheme with an explicit expression of these negative preferences, so that we
can simultaneously decipher the popularity as well as the polarity of each
candidate. The winner is picked by an optimal tradeoff between the most
popular and the least polarizing candidate. By penalizing the candidates for
their polarization, we can discourage the divisive campaign rhetorics and pave
way for potential third party candidates.

Social choice theorists have pondered over alternate voting systems for more
than two centuries since Nicolas de Condorcet Condorcet (1785). The ranked
voting systems, wherein the voters rank their choices instead of just voting
for their first preference, have been thoroughly explored and their
deficiencies have been mathematically nailed down. Arrow’s Impossibility
theorem Arrow (1950) proves that it is impossible to always pick a winner in a
ranked voting system that satisfies certain basic intuitive criteria. Further,
the Gibbard-Satterthwaite (GS) theorem Gibbard (1973); Satterthwaite (1975)
proves that in any ranked voting system, some voters can always strategically
misrepresent their votes to alter the results, which implies an impossibility
of a _strategy-proof_ voting system. So, it appears that there cannot exist a
voting system that fairly represents the voter preferences, prompting the
notion that a perfect democracy is mathematically impossible.111The Stanford
Encyclopedia of Philosophy provides a good nontechnical introduction to
various voting systems. https://plato.stanford.edu/entries/voting-methods/

It may very well be true that we cannot design a perfect voting system,
nevertheless we can certainly do much better than the naive _plurality voting_
system wherein the voters only vote for their first preference. Any alternate
voting method is of course more complex, but the advent of electronic voting
vastly simplifies its implementation. So there is no valid excuse to not
facilitate smarter and fairer elections.

The major problem with the plurality voting system is that when two strong
candidates emerge with certain critical mass of support prior to the election,
then rest of the support will automatically coagulate around them, simply
because many voters don’t want to waste their votes on a third candidate. This
is very deceptive because many of those votes are not direct support for the
respective candidates, rather they are anti-votes against the opposing
candidate. To make matters worse, the candidates understand this phenomenon
and indulge in some divisive campaign rhetorics to collect more of their
opponent’s anti-votes. Many voters would thus strategically refrain from
voting for their real preference (the third party candidate) because their
priority is to defeat one of the top two contenders by voting for the other.
Consequently, the third party candidates are stifled out of competition.

Ranked voting systems alleviate this issue significantly because the voters
have the opportunity to elaborate their preferences in a more detailed
fashion. The voters can express their dislike for a candidate by ranking them
the last, however this is not the same as explicitly casting a negative vote.
The only way to prevent the anti-votes for a candidate from being masked into
votes for another candidate is to explicitly express them on the ballot as
negative votes.

Moreover, it is well established that people’s choice very much depends on how
the decision problem in front of them is framed Tversky and Kahneman
(1981)222For example, people make completely different choices when a problem
is framed as an increase in monetary gain as opposed to avoiding monetary
loss.. By not allowing the voters to freely express their negative
preferences, we are essentially ill-framing the decision problem and
needlessly tampering with voter’s psychology. Here I shall propose a voting
system which explicitly incorporates negative votes.

Normed Negative Voting :  Consider a voting system where each voter assigns a
positive or negative number to each candidate such that the magnitudes of all
the numbers sum up to 10.

Example : In a three candidate election amongst $\\{A,B,C\\}$, voter-1 could
vote as $\\{+7,-1,-2\\}$ while voter-2 could vote as $\\{+3,+2,-5\\}$. Both
the voters express the same rank ordering of preferences, namely $A>B>C$,
however their ballots clearly contain far richer information than just the
relative ranks. Requiring the sum of magnitudes of the vote to be a constant
(10) is mathematically termed as _Normed_ ; it serves to ensure the rule of
equality _one-person-one-vote_.

Vote aggregation :  For each candidate, aggregate the positive votes from all
voters as P, and aggregate the negative votes from all voters as N. Then
define for each candidate _Popularity_ $\equiv$ P-N, and _Polarity_ $\equiv$
N/P. An absolutely noncontroversial candidate who does not acquire any
negative votes will have the lowest polarity of zero. On the other hand, a
candidate with almost equally large positive and negative votes is by
definition extremely polarizing with a polarity of 1. For obvious reasons,
candidates with polarity larger than 1 should be disqualified.

Winning metric :  To determine the winner, we shall construct a metric W that
rewards popularity and penalizes polarity. It has to be a monotonically
increasing function of popularity and a monotonically decreasing function of
polarity. The candidate with the highest value of W is the winner. If two
candidates have equal popularity, the one with lower polarity will have to
win. Consider the following metric parametrized by two positive constants
$(c,b)$.

$W_{b}^{c}(P,N)\equiv\frac{P-cN}{1+b\,N/P}$ (1)

Let us first examine this function with $c=b=1$. Consider an election with
three candidates and two voters as shown below.

Candidate | voter-1 | voter-2 | P | N | P-N | N/P | $W_{1}^{1}$
---|---|---|---|---|---|---|---
A | 10 | -5 | 10 | 5 | 5 | 0.5 | 3.33
B | 0 | 4 | 4 | 0 | 4 | 0 | 4
C | 0 | 1 | 1 | 0 | 1 | 0 | 1

Although A has the highest popularity, B still wins over A because of lower
polarity. This seems to be a fair result for this election. However, we should
note that this voting scheme is severely prone to strategic-voting. Voter-1
has naively expressed a clear preference for A and no dislike for B. On the
other hand, voter-2 might simply prefer B over A (and no real dislike for A),
however by misrepresenting the preference and casting a negative vote to
increase the polarity of A, voter-2 can enhance the chances of B’s victory.
Game-theoretically speaking, voter-1 would foresee this and in turn
misrepresent his preference to include a negative vote for B. 333When there
are more than two candidates it is difficult to strategically cast negative
votes without hampering the positive votes for the preferred candidate, which
could inhibit the winning chances of the preferred candidate.

Avoid over-penalization of Negative Votes :  Strategically misrepresenting the
negative votes as described above should be discouraged. It cannot be
completely eliminated, but it can be suppressed by appropriately constraining
the winning metric. We should ensure that the winning metric does not over-
penalize the negative votes because that would give the voters an opportunity
to exploit it. In order to quantify what exactly we mean by “over-penalize”,
let us first note that plurality voting method is indeed the optimal voting
scheme in a two-candidate election. So we shall demand that a perfect
preference for a candidate by one voter cannot be overridden by another
voter’s negative vote. To be more specific,

  * •

_In a 2-candidate election with just two voters, if voter-1 gives a perfect
preference for one candidate, then that candidate cannot loose the election
regardless of how voter-2 votes._

To work out this constraint, let voter-1 cast +10 votes for A and voter-2 cast
a negative vote -X for A as shown below.

Candidate | voter-1 | voter-2 | P-cN | N/P | $W_{b}^{c}$
---|---|---|---|---|---
A | 10 | -X | 10-cX | $X/10$ | $10\left(\frac{10-cX}{10+bX}\right)$
B | 0 | 10-X | 10-X | 0 | 10-X

For any value of $X$ between 0 and 10, we demand that candidate B should not
be able to win.

$\displaystyle\left(\frac{10-cX}{1+b\,X/10}\right)\geq(10-X)$ (2)
$\displaystyle\Rightarrow\frac{c+b-1}{b}\leq X/10$ (3)
$\displaystyle\Rightarrow c+b\leq 1$ (4)

Since B cannot win anyway, the best option for voter-2 is to choose $X=0$, so
that A and B are tied up.

We can now generalize the constraint for $m$ candidates and a large number of
voters. Again, let voter-1 assign +10 votes to A, and voter-2 assign -X votes
to A. The reminder of 10-X votes of voter-2 can be assigned as positive votes
for any of the other $(m-1)$ candidates. Here voter-2 should be viewed as a
statistical representative of all voters who voted -X for A; and all these
voters are assumed to be independent minds uninfluenced by each other. On
average, each of the other candidates would have received $(10-X)/(m-1)$ votes
from voter-2. So, the above constraint can be reframed at a statistical level
as

$\displaystyle\left(\frac{10-cX}{1+b\,X/10}\right)\geq\frac{(10-X)}{m-1}\,\,\Rightarrow$
$\displaystyle m-2\geq[(m-1)c+b-1]X/10-b(X/10)^{2}$ (5)

In eq.3 the r.h.s attains a minimum at X=0, which is where the equality should
be implemented. But that is not true in eq.5 when $m>2$. The acceptable range
of parameters (c,b) for which eq.5 holds for all values of X is plotted in
fig.1 for $m=2,3,4,5$; the region under the curves corresponding to each $m$
contain the admissible values for the parameters. First we note the obvious,
that $c$ cannot be greater than 1 because negative votes shouldn’t weigh more
than positive votes. For $m=2$, note that $c=1$ is admissible only with $b=0$.
But for $m>2$, $c=1$ is admissible for any $b\leq m-2$. In particular, note
that $(c=1,b=1)$ is acceptable for all $m>2$. By choosing the parameters on
the curves of fig.1, we are hitting the limit of over-penalization of negative
votes; so these curves are essentially the _maximal-penalty_ metrics.

Figure 1: Maximal-Penalty metrics

Here we have only analyzed the winning metric function of the form eq. 1. But
it is fairly straightforward to imagine other functional forms that introduce
nonlinearities to penalize the negative votes more adversely, like

$\frac{(P-N)}{e^{N/P}},\,\,\,\frac{(P-N)^{2}}{(P+N)},\,\,\,(P-N)^{1-N/P}.$ (6)

The first two are acceptable, but the third is not acceptable because the
metric function must overall be linear in popularity so that its properties do
not depend on the size of the electorate. These functions can be analyzed in a
procedure similar to that discussed above with introduction of some free
parameters (analogous to $c,b$) to ensure that negative votes are not over-
penalized. The maximal-penalty metrics thus obtained show similar qualitative
behavior as shown in fig.1, so there is not much utility to further discuss
these alternate functional forms of metric.

## Maximizing Voter satisfaction

Let’s denote the voters by latin indices $i,j,k...$ and the candidates by
greek indices $\mu,\nu,\alpha...$. Let’s denote the positive votes from
voter-$i$ to candidate-$\mu$ as $p^{i}_{\mu}$, and the negative votes as
$n^{i}_{\mu}$. Only one of the two, $p^{i}_{\mu}$ or $n^{i}_{\mu}$, will be
nonzero for a specific $i$ and $\mu$. Summing over all the voters will give
the net positive votes $P_{\mu}=\sum_{i}p^{i}_{\mu}$ and net negative votes
$N_{\mu}=\sum_{i}n^{i}_{\mu}$ gathered by each candidate-$\mu$.

If candidate-$\alpha$ is declared the winner of the election, we define can
define the voter-satisfaction to be

$\displaystyle
s^{i}_{\alpha}=p^{i}_{\alpha}-n^{i}_{\alpha}+\sum_{\mu}^{\mu\neq\alpha}n^{i}_{\mu}$
$\displaystyle
S_{\alpha}=\sum_{i}s^{i}_{\alpha}=P_{\alpha}-N_{\alpha}+\sum_{\mu}^{\mu\neq\alpha}N_{\mu}$
(7)
$\bar{S}_{\alpha}=S_{\alpha}-\left[\sum_{\mu}^{\mu\neq\alpha}P_{\mu}\right]$
(8)

The first two terms in the r.h.s of eq. 7 correspond to the
satisfaction/dissatisfaction explicitly triggered by the winning candidate,
while the third term represents the satisfaction triggered by all the loosing
candidates. Negative votes are directly responsible for a candidate to loose
the election, and so those negative votes assigned to loosing candidates can
be deemed to have satisfactorily performed their job, and hence contributes to
the voter satisfaction as the third term in the r.h.s of eq. 7.

One might be tempted to include the dissatisfaction due to the positive votes
accrued by the loosing candidates as shown in eq. 8. But notice that it is a
measure of _inaction_ of certain positive votes that failed to deliver
victory. It should be treated simply as a lack of satisfaction that was
potentially attainable, rather than a negative quantity to be subtracted from
voter satisfaction. While defining the voter satisfaction, it is critical to
acknowledge the intrinsic asymmetry between the positive and negative votes in
the voter’s psychology– _positive votes succeed only when they are cast to the
winner, but negative votes succeed when they are cast to any loser._

Ideally we would like the election outcome to maximize the satisfaction of all
voters, _i.e._ $S_{\alpha}$ should be maximum for the winning
candidate-$\alpha$. Notice that if we only considered the first two terms in
the r.h.s of eq.7, then we simply have to maximize the popularity given by
$(P_{\alpha}-N_{\alpha})$, which is exactly what the winning metric
$W_{0}^{1}$ would implement. It is however not obvious whether some other
winning metric will always yield the winner who maximizes voter satisfaction.
Consider an example of a 4-candidate election with aggregated positive and
negative votes as shown below.

_Election-0_

Candidate | P | N | $S$ | $W_{0}^{1}$ | $W_{1}^{1}$ | $W_{2}^{1}$ | $W_{0.5}^{0.5}$
---|---|---|---|---|---|---|---
A | 11 | 5 | 10 | 6.0 | 4.12 | 3.14 | 6.92
B | 7 | 3 | 10 | 4.0 | 2.8 | 2.15 | 4.53
C | 6 | 1 | 13 | 5.0 | 4.28 | 3.75 | 5.08
D | 3 | 0 | 12 | 3.0 | 3.0 | 3.0 | 3.0

Here, candidate-C has the maximum voter satisfaction, and also wins under the
metrics $W_{1}^{1}$ and $W_{2}^{1}$. But this may not always happen; in some
elections the winning metrics may not yield the candidate who maximizes voter
satisfaction. To understand how reliably these metrics correlate to maximal
voter satisfaction, we shall simulate a large number of $m$-candidate
elections with randomly distributed $(P_{\mu},N_{\mu})$ with at least one
candidate qualified to win. Then we calculate the probability that a winning
metric yields a winner who maximizes the voter satisfaction. Table 1 shows the
results for four different metrics and various values of $m$.

| $W_{0}^{1}$ | $W_{1}^{1}$ | $W_{2}^{1}$ | $W_{0.5}^{0.5}$
---|---|---|---|---
$m=3$ | 87% | 91% | 86% | 80%
$m=4$ | 84% | 89% | 87% | 76%
$m=5$ | 82% | 88% | 88% | 73%
$m=8$ | 79% | 88% | 91% | 70%
$m=20$ | 79% | 91% | 93% | 70%
Table 1: Winning Metrics Correlation to Maximal Voter Satisfaction

Interestingly, the metrics $W_{1}^{1}$ and $W_{2}^{1}$ perform better in
aligning with voter satisfaction for larger values of $m$, while this effect
is not seen in $W_{0}^{1}$. This suggests that the effect of polarity in the
functional form of the metric (denominator of eq. 1) truly captures the voter
satisfaction in a very non-obvious way. This is indeed nontrivial because the
metric is a function of only the votes obtained by any particular candidate,
but voter satisfaction is a function of votes obtained by all candidates. It
is also very clear from the performance of $W_{0.5}^{0.5}$ that a metric with
$c<1$ is suboptimal. The most suitable metric that remains within the maximal
penalty limit and works for all $m\geq 3$ is the metric $W_{1}^{1}$.

If we altered our definition of voter satisfaction to be $\bar{S}_{\alpha}$ in
eq. 8, we find that the winner picked by $W_{0}^{1}$ almost always maximizes
voter satisfaction. So, whether or not the metric function should penalize
polarity (eq.1) very much depends on our definition of voter satisfaction.

More generally, we could ask the following question– if the aim is to pick the
candidate who would maximize the voter satisfaction, then why do we need to
pick the winner in a round-about manner using a winning metric, rather than
directly picking the candidate maximizing the voter satisfaction? This is
because the prescription of a winning metric a priori informs the voters how
much their negative votes weigh against their positive votes. Without a
winning metric we wouldn’t have a tool to discourage the voters from strategic
voting.

## Comparison with Ranked Voting

It is straightforward to convert the normed negative votes into ranked votes,
as long as voters cast distinct votes to various candidates. For example,
consider the 4-candidate election with three voters as shown below.
Candidate-B is the winner according to the metrics $W_{0}^{1}$, $W_{1}^{1}$
and the voter satisfaction.

_Election-1_ Candidate voter-1 voter-2 voter-3 Borda $W_{0}^{1}$ $W_{1}^{1}$ S
A 5 [1] -5 [4] 3 [2] 3+0+2 3.0 1.84 6 B 2 [2] 0 [3] 4 [1] 2+1+3 6.0 6.0 14 C 1
[3] 1 [2] -2 [4] 1+2+0 0.0 0.0 6 D -1 [4] 4 [1] 1 [3] 0+3+1 4.0 3.33 11

The rank corresponding to each vote is expressed in square brackets next to
the vote. Let us now bypass the vote itself and only consider the ranks. There
are different ways to pick a winner in a ranked voting system. In _Condorcet_
method Fishburn (1977), we split the $m$-candidate race into a bunch of
2-candidate head-to-head competitions. The winner is the candidate who wins
every head-to-head competition. In the above example, voter-1 ranks A higher
than B while voter-2 and voter-3 rank B higher than A; hence B defeats A.
Similarly B defeats C and D in head-to-head competitions.Thus candidate-B is
the Condorcet winner in this example. However, there are many situations where
this procedure does not yield a clear winner, and we end up in a rock-paper-
scissor configuration of cyclic loop of winners.

In _Instant Runoff_ , votes are counted in multiple stages. In each stage, the
candidates with the least number of rank-1 votes get eliminated, and
subsequently the ranks of all other candidates are boosted up by one in those
ballots that had the eliminated candidate in the rank-1 position. So, the
voter’s ballot is not eliminated after the first preference is eliminated,
instead the subsequent preferences are considered in order. In the above
example, candidate-C gets eliminated in the first round with zero rank-1
votes, and A, B & D end up in a tie. Such a tie situation is unlikely when
there are many voters, and the counting will proceed to next stage of
elimination. For instance if there were two voters who vote like voter-3, then
A and D get eliminated in the second stage with just one rank-1 vote each,
leaving candidate-B the winner.

A major issue with Instant Runoff is that it does not satisfy the basic
criterion of _monotonicity_. That is, a winning candidate can become a looser
by getting ranked higher by a voter, which is intuitively strange and
unacceptable. It happens because a stronger candidate survives an earlier
stage of elimination due to the rank modifications. This gives a lot of leeway
for the voters to strategically attempt to eliminate strong opposition
candidates at earlier stages of elimination, rather than vote according to
their innate preferences. It is of course very difficult to strategize for
multistage elimination with a large number of voters, but there is nothing
stopping the voters from attempting to strategize. Any procedure which calls
for multistage elimination of candidates is prone to this issue. The GS
theorem Gibbard (1973) shows that it is not possible to totally prevent
strategic voting, but we can curtail it significantly by satisfying the
monotonicity criterion.

_Borda_ proposed a metric that aggregates a weighted sum of the ranks accrued
by each candidate Borda (1784). In an $m$-candidate race, rank-1 gets a weight
$(m-1)$, rank-2 gets a weight $(m-2)$ and so on, with rank-m ending at weight
zero. In the above example, candidate A has accrued one rank-1, one rank-4 and
one rank-2, yielding a net Borda count of 3+0+2 =5; while B attains a Borda
count of 6 and wins the election. Borda metric satisfies the monotonicity
criterion, but it violates another intuitive criterion, _Independence of
Irrelevant Alternatives_ (IIA).

The IIA criterion requires that if the voters were allowed to modify their
votes without changing the relative preference between a winning candidate and
a specific looser, then that looser shouldn’t be able to win due to the vote
modifications. Suppose candidate-$\alpha$ is the winner and is ranked higher
than a loosing candidate-$\mu$ by some voter, then no matter how the voter
changes the ranks while holding $\alpha$ higher than $\mu$, there should be no
chance for candidate-$\mu$ to win. The Condorcet method of counting the head-
to-head competitions only cares about the relative rankings, hence it will
satisfy IIA criterion. Any other method that weighs the absolute rank
positions, like the Borda metric, will violate this criterion. The IIA
criterion seems overrated for its intuitiveness, primarily because it is a
necessary condition for Arrow’s impossibility theorem which proves that it is
not always possible to find a winner in a ranked voting election when certain
intuitive conditions are met Arrow (1950); Fishburn (1970); Reny (2001).

The normed negative voting (NNV) method in this article would not satisfy the
IIA criterion, because these votes are cardinal in nature, which represents
much richer information than relative ranking. Hence it is not subject to
implications of Arrow’s theorem Arrow (1950). Furthermore, the NNV also
violates the monotonicity criterion. If a voter increases the positive votes
for the winner, then obviously the winning metric value as calculated by eq. 1
would further increase. But any increase in positive votes for the winning
candidate must be compensated by a decrease in votes to other candidates, as
per the normed voting rules. Let’s suppose that the negative votes to another
candidate is reduced. It is now possible for this candidate to emerge as the
new winner, if $c+b>1$. This violates the monotonicity criterion. However,
notice that this is precisely what we prevented at a statistical level, by
restricting the metric to stay under maximal penalty (eq. 5). Although the
monotonicity criterion does not hold at individual instances, it holds on
average with large number of voters. That is why it is not possible to
strategically exploit the negative votes without large scale coordinated
effort among voters.

In _Approval voting_ method, the voters can approve of any number of
candidates and disapprove of the others, and every approved candidate gets +1
vote. In a way, this violates the basic principle of _one-person-one-vote_.
But we can rectify the method by assigning -1 vote to every disapproved
candidate, thereby revising it as normed-Approval voting. We can view this as
a special case of the NNV procedure with a uniform magnitude of positive or
negative vote for every candidate, which is clearly an unnecessary restriction
on voter expression.

The NNV method gathers the voter preferences in a very rich format. To
emphasize this, let’s modify the votes of voter-2 in the previous example of
_Election-1_ without affecting the relative ranks, as shown below.

_Election-2_ Candidate voter-1 voter-2 voter-3 Borda $W_{0}^{1}$ $W_{1}^{1}$ S
A 5 [1] -1 [4] 3 [2] 3+0+2 7.0 6.2 10 B 2 [2] 0 [3] 4 [1] 2+1+3 6.0 6.0 10 C 1
[3] 1 [2] -2 [4] 1+2+0 0.0 0.0 2 D -1 [4] 8 [1] 1 [3] 0+3+1 8.0 7.2 11

Candidate-B is still the winner under all the ranked voting methods discussed
above. But candidate-B looses to both A and C under NNV metrics $W_{0}^{1}$,
$W_{1}^{1}$, and the voter satisfaction. _Election-1_ is identical to
_Election-2_ under ranked voting methods, but very different under NNV. This
clearly illustrates the effect of superficially considering the ranks while
ignoring the deeper negative preferences of voters. It is also not difficult
to imagine the frustration that would develop among the voters if their votes
aligned with _Election-2_ , but ranked voting method results in B’s victory,
which is aligned with _Election-1_.

## Conclusion

I have discussed the importance of negative votes in capturing the voter
preferences in a richer format. To prevent voters from exploiting the negative
votes for strategic voting, we constrained the winning metric to avoid over-
penalization of the negative votes. Since the negative votes for the disliked
candidates come at the expense of positive votes for their preferred
candidates, the voters are incentivized to vote according to their true
preference, suppressing the intent for strategic voting.

This would also have a serious impact on how election campaigns are conducted.
For the fear of accumulating negative votes, the candidates would refrain from
divisive rhetorics and stay focused on constructive issues. The major parties
cannot afford to nominate a polarizing candidate because they understand that
it would directly pave way for a third party victory. The whole political
arena can thus be depolarized.

The candidates will stay well-behaved by conducting decent campaigns and the
voters will stay well-behaved by voting their true preferences. We can then
hope for a future where no candidate receives any negative vote. – _Dream of
an Ideal society_.

## References

  * Condorcet (1785) M. d. Condorcet, Paris: Imprimerie Royale (1785).
  * Arrow (1950) K. J. Arrow, Journal of political economy 58, 328 (1950).
  * Gibbard (1973) A. Gibbard, Econometrica: journal of the Econometric Society 41, 587 (1973).
  * Satterthwaite (1975) M. A. Satterthwaite, Journal of economic theory 10, 187 (1975).
  * Tversky and Kahneman (1981) A. Tversky and D. Kahneman, science 211, 453 (1981).
  * Fishburn (1977) P. C. Fishburn, SIAM Journal on applied Mathematics 33, 469 (1977).
  * Borda (1784) J.-C. d. Borda, Histoire de l’Academie Royale des Sciences pour 1781 (Paris, 1784) (1784).
  * Fishburn (1970) P. C. Fishburn, Journal of Economic Theory 2, 103 (1970).
  * Reny (2001) P. J. Reny, Economics letters 70, 99 (2001).