1]Department of Mathematics and Computer Science, Saarland University,
Saarbruecken, Saarland, Germany

2]Agents and Simulated Reality Department, German Research Center for
Artificial Intelligence (DFKI), Saarbruecken, Saarland, Germany

# Nav-Q: Quantum Deep Reinforcement Learning for Collision-Free Navigation of
Self-Driving Cars

Akash Sinha  Antonio Macaluso<EMAIL_ADDRESS>Matthias Klusch  [  [

###### Abstract

The task of collision-free navigation (CFN) of self-driving cars is an NP-hard
problem usually tackled using Deep Reinforcement Learning (DRL). While DRL
methods have proven to be effective, their implementation requires substantial
computing resources and extended training periods to develop a robust agent.
On the other hand, quantum reinforcement learning has recently demonstrated
faster convergence and improved stability in simple, non-real-world
environments.

In this work, we propose Nav-Q, the first quantum-supported DRL algorithm for
CFN of self-driving cars, that leverages quantum computation for improving the
training performance without the requirement for onboard quantum hardware.
Nav-Q is based on the actor-critic approach, where the critic is implemented
using a hybrid quantum-classical algorithm suitable for near-term quantum
devices. We assess the performance of Nav-Q using the CARLA driving simulator,
a de facto standard benchmark for evaluating state-of-the-art DRL methods. Our
empirical evaluations showcase that Nav-Q surpasses its classical counterpart
in terms of training stability and, in certain instances, with respect to the
convergence rate. Furthermore, we assess Nav-Q in relation to effective
dimension, unveiling that the incorporation of a quantum component results in
a model with greater descriptive power compared to classical baselines.
Finally, we evaluate the performance of Nav-Q using noisy quantum simulation,
observing that the quantum noise deteriorates the training performances but
enhances the exploratory tendencies of the agent during training.

###### keywords:

Quantum Reinforcement Learning, Collision Free Navigation, Autonomous Driving,
Quantum Artificial Intelligence

##  1 Introduction

The pursuit of autonomous navigation for self-driving cars has ushered in a
new era of transportation, promising safer and more efficient journeys.
Central to this endeavor is the challenge of collision-free navigation (CFN),
a complex optimization problem that lies at the heart of ensuring the safety
and reliability of autonomous vehicles. Over the years, significant strides
have been made in tackling this problem, with researchers and engineers
harnessing the power of computational methods to chart paths that avoid
obstacles and minimize risks [1, 2, 3].

In the domain of autonomous navigation, a prevalent approach involves
conceptualizing the problem as Partially Observable Markov Decision Processes
(POMDPs) [4, 5] which poses a significant computational challenge when dealing
with real-world scenarios. The current state-of-the-art solutions rely on Deep
Reinforcement Learning (DRL) [1, 2, 3], which can be integrated with POMDP
planning [4, 5]. While these techniques have demonstrated promising results,
they demand substantial computing resources and training time to develop a
robust reinforcement learning (RL) agent.

In parallel, the field of quantum reinforcement learning (QRL) has recently
emerged as an innovative paradigm that harnesses the computational
capabilities of quantum computing in conjunction with the principles of
reinforcement learning (RL). Early experiments [6, 7, 8, 9] have showcased the
potential of QRL methods to accelerate training times when applied to
simplified, non-real-world environments, often exemplified by the benchmark
domains provided by OpenAI Gym [10]. However, a critical gap remains to be
bridged as none of these methods have been tested in the challenging, real-
world environment as the one of CFN of self-driving cars. Furthermore, many of
the suggested methodologies presuppose the substitution of traditional neural
networks, which provide action directives, with parametrized quantum circuits
(PQCs). In the context of CFN, this implies the requirement of a quantum
computing device installed onboard the vehicle for experimentation—a
requirement that is impractical to fulfill.

This paper delves into the feasibility and potential advantages of quantum-
supported DRL within the domain of CFN of self-driving cars. Specifically, we
introduce a novel quantum-supported architecture that leverages quantum
computation during training, resulting in state-of-the-art performance during
testing. Precisely, the contributions are the following:

  1. 1.

Introducing Nav-Q, the first quantum-supported Deep Reinforcement Learning
(DRL) approach that combines quantum and classical neural networks to tackle
the CFN problem of self-driving cars. Nav-Q employs an actor-critic algorithm,
with the critic implemented through a hybrid quantum-classical approach,
enhancing the performance during training without requiring an onboard quantum
device for testing.

  2. 2.

Extend the Data Reuploading technique [11] by proposing a new encoding
strategy for quantum embedding named Qubit Independent Data Encoding and
Processing (QIDEP), allowing for the versatile encoding of high-dimensional
classical data while providing flexibility in the number of qubits used.

  3. 3.

Train and evaluate Nav-Q on the CARLA-CTS1.0 benchmark [5], a widely
recognized standard for testing DRL models in the context of self-driving
cars. Nav-Q’s performance is compared with its natural classical counterpart,
NavA2C (Section 3.3), which exclusively utilizes classical computational
resources. The comprehensive results indicate that Nav-Q demonstrates improved
stability across various initializations of the architecture and, in some
instances, a faster convergence rate. Additionally, Nav-Q attains state-of-
the-art performance in the driving policy while substantially reducing the
number of parameters. It also showcases a heightened potential for
learnability when evaluating effective dimension as a metric to assess the
model’s ability to learn complex patterns from data.

  4. 4.

Train Nav-Q on a simulated noisy quantum system with the parameter-shift rule
to estimate the expected performance when experiments are performed on near-
term quantum hardware.

The rest of the paper is structured as follows. A discussion of the related
works, quantum and classical, is reported in Sect. 2. This is followed by the
formalization of the CFN problem as a POMDP and a detailed description of an
advanced classical solution named NavA2C, which serves as the classical
baseline, in Section 3. Our quantum-supported solution Nav-Q is described in
Sect. 4 and its performance comparatively evaluated in Sect. 5. Section 6
concludes with a summary of achievements and future work.

##  2 Related Works

In this section, we provide a summary of the existing literature relevant to
two key aspects of this paper’s contributions. The first part delves into
current state-of-the-art approaches for addressing the CFN problem, primarily
centered around DRL algorithms. Secondly, we explore the QRL landscape, which
focuses on training parameterized quantum circuits to function as agents
within classical environments.

###  2.1 Deep Reinforcement Learning for Collision-Free Navigation

The state-of-the-art approach for addressing the CFN problem of self-driving
cars typically involves formulating it as a POMDP and solving it through DRL.
Different approaches are possible depending on the specific problem the DRL
algorithm is tasked with, ranging from simple lane following to complex tasks
like end-to-end driving in urban scenarios [1, 2, 3]. These methods exhibit
variations in the DRL algorithm used, system architecture, reward design,
tasks, input, and actions performed by the agent.

Recently, different actor-critic-based architectures for DRL have been
proposed. In particular, A3C approaches [12, 13] execute on multiple parallel
instances of the environment to use the parallel actor-learners for
stabilizing effect on training process. The adaptation of this approach in the
context of CFN is referred to as GA3C-CADRL [14] and has been tested for
mobile robot navigation. In this case, the observation of the environment is
not presented as a picture image but rather as the position, velocity, and
orientation of the robot. Also, an LSTM [15] is used to encode temporal and
spatial data in this scenario. Alternatively, A2C is the synchronous version
of the A3C model, that waits for each agent to finish its experience before
conducting an update. In this respect, A2C-CADRL-p has been recently
introduced [5] as a synchronous variant of GA3C-CADRL that utilizes the output
of path planning and the perceived environment as input to the network, as
opposed to end-to-end learning, enabling the agent to navigate the environment
with a specific goal.

Beyond A2C and A3C approaches, whose performance are comparable, recent work
has highlighted Proximal Policy Optimization (PPO) as a standout approach for
self-driving cars [16, 17]. PPO excels due to its stability, sample
efficiency, and adaptability to continuous action spaces. By preventing large
policy updates, it ensures stable learning, particularly crucial for safety-
critical applications. Moreover, its compatibility with parallel processing
accelerates learning in data-intensive scenarios.

At the time of writing this paper, Pennylane [18] with the PyTorch plugin did
not support parameter
broadcasting111https://docs.pennylane.ai/en/stable/code/api/pennylane.broadcast.html.
Consequently, the quantum version of PPO, which requires batch processing of
data through quantum circuit simulations, incurred a substantial time cost on
classical computers, rendering training these algorithms impractical.
Therefore, for practical purposes, our focus is on the classical baseline
NavA2C (see Section 3.3) based on A2C-CADRL-p [5]. This approach combines a
symbolic path planner and a modified A2C agent in one architecture, with the
DRL agent solely responsible for the speed action. Nevertheless, the Nav-Q
methodology (described in Section 4) utilizes an actor-critic model and can be
seamlessly adapted to the PPO approach, provided that the available quantum
software tools support efficient parameter broadcasting.

###  2.2 Quantum Reinforcement Learning

The standard approach in Quantum Reinforcement Learning (QRL) consists of
replacing a classical Neural Network with a Parametrized Quantum Circuit (PQC)
to enhance performance in terms of trainability, stability, and learning
policy.

Among the various alternatives, the use of a Quantum Q-Learning algorithm has
been investigated and compared to a Deep Q-Network, revealing a parameter
space complexity of PQCs scaling as $\mathcal{O}(N)$, in contrast to the
$\mathcal{O}(N^{2})$ complexity of classical DQN [8]. This investigation
focused on PQCs operating in a straightforward deterministic environment with
a single input value, where both the observation space and output space were
restricted to the same number of quantum bits. In a subsequent study [19],
alternative PQC architectures and encoding schemes were explored, extending
the algorithm’s testing to slightly more complex environments. Another
advancement involved a novel data encoding scheme using trainable weights,
enhancing Quantum Q-Learning performance [9]. In a different vein, a Quantum
Soft Actor-Critic algorithm has been proposed [7], where the actor was
implemented as a PQC, and the critic utilized a classical neural network.
Another study proposed the Softmax-PQC, employing a softmax policy to
successfully address various standard RL tasks based on REINFORCE [20, 6].
Additionally, a QRL algorithm based on PPO [16] has been introduced, with the
actor implemented using a PQC and the critic with a classical neural network
[21, 22]. Lastly, the use of Q-SAC to control a simulated robotic arm with
continuous action and state spaces was demonstrated [23].

Environment |  | Observation
---
Space
| Observation
---
Shape
Action Space |  | Action
---
Shape
Acrobot | Continuous | (6,) | Discrete(3) | (1,)
BlackJack |  | Tuple(Discrete(32),
---
Discrete(11),
Discrete(2))
(3,) | Discrete(2) | (1,)
CartPole | Continuous | (4,) | Discrete(2) | (1,)
FrozenLake | Discrete(16) | (1,) | Discrete(4) | (1,)
MountainCar | Continuous | (2,) | Discrete(3) | (1,)
Pendulum | Continuous | (3,) | Continuous | (1,)
|  |  |  |
Table 1: An overview of the characteristics of the environments used to
evaluate the performance of existing quantum reinforcement learning methods.

All current QRL methods, as summarized in Table 1, have been assessed in the
context of OpenAI Gym environments. These environments are characterized by
being static, fully observable, and featuring a low-dimensional state space.
However, the CFN problem of self-driving cars is dynamic, partially
observable, and involves high-dimensional observations and state spaces. As a
result, existing QRL algorithms fall short in effectively addressing CFN
problems. Moreover, PQCs primarily serve to determine the actions that an
agent should take within an environment. Even when adapting existing QRL
methods for more intricate problems, incorporating a Quantum Processing Unit
(QPU) into the car becomes a necessity in algorithm design. However, this
requirement is impractical given the current challenges associated with
building a real QPU. Therefore, our goal is to introduce a novel method
capable of harnessing the potential advantages of quantum computing within the
realm of CFN without the need to install a QPU in cars.

##  3 Problem Formulation

Collision-free navigation (CFN) refers to the task of driving on a drivable
path from one location to another while minimizing time to goal and the number
of collisions with static and dynamic obstacles. CFN task can be modeled as a
POMDP [4, 5] problem that requires a formal definition of the car model,
pedestrian model, and environment.

###  3.1 Car and Pedestrian Model

The Car state is defined as a 4-tuple ($p^{c}_{t}$, $p^{c}_{goal}$,
$v^{c}_{t}$, $\theta^{c}_{t}$) where $p^{c}_{t}$ $\in\mathbb{R}^{2}$ is the
current position, $p^{c}_{goal}$ $\in\mathbb{R}^{2}$ is the goal position,
$v^{c}_{t}$ $\in\mathbb{R}$ the speed and $\theta^{c}_{t}$ $\in$ [0, 2$\pi$)
the orientation of the car at instance $t$. The car uses the bicycle model to
approximately model the car driving on the road. We assume for the sake of
this work that the car can detect all unoccluded static and dynamic obstacles
within a radius of 50 m. The vehicle has a 360-degree view of its
surroundings. However, in the case of dynamic obstacles, only its current
position is visible; the car’s perception model is unable to see the
obstacle’s goal position or the potential direction in which it might move.
Additionally, we assume that all available sensor data is noise-free. For
goal-directed navigation of the driverless car, we use the Anytime Weighted
Hybrid A* Path Planner to calculate a driveable path for the car from source
to destination. This planner needs a 2-dimensional discretized cost map of the
environment to plan the route. Our basic cost-map converts environmental data
from the actual scene to a discretized grid map from a bird’s eye view, with
obstacle costs of car states defined as maximum of 1, 50, and 100,
respectively, if the car is entirely on the road, partially on the sidewalk,
and collides with an obstacle anywhere else.

The pedestrian state is represented by a 4-tuple
$(p_{\text{t}}^{ped},p_{\text{goal}}^{ped},v_{\text{t}}^{ped},\theta_{\text{t}}^{ped})$,
where $p_{\text{t}}^{ped}\in\mathbb{R}^{2}$ is the current position of the
pedestrian, $p_{\text{goal}}^{ped}\in\mathbb{R}^{2}$ is the goal position of
the pedestrian, $v_{\text{t}}^{ped}\in\mathbb{R}$ is the speed of the
pedestrian and $\theta_{\text{t}}^{ped}\in[0,2\pi)$ is the orientation of the
pedestrian at time instance $t$. We assume that the pedestrians move towards
the goal in a straight line.

###  3.2 Collision-free navigation problem

The problem of CFN can be formulated as a POMDP$(S,A,T,R,\gamma,Z,O)$ as
follows:

$S$: Represents the set of states,
$\\{[c,\text{ped}_{1},\ldots,\text{ped}_{|P|}]|c\in\mathbb{R}^{2}\times\mathbb{R}^{2}\times[0,2\pi),\text{ped}_{i}\in\mathbb{R}^{2}\times\mathbb{R}^{2}\times\mathbb{R}^{2}\times[0,2\pi),1\leq
i\leq|P|\\}$, where $c$ denotes the car’s state at time $t$, and
$\text{ped}_{i}=[\text{ped}_{o}^{i},\text{ped}_{h}^{i}]$ represents the
observable and hidden state of pedestrian $i$ ($1\leq i\leq|P|$).

$A$: Denotes the set of all possible actions. Each action $a\in A$ is defined
as a 2-tuple $(\alpha,\text{acc})$, where $\alpha$ is the steering angle and
acc is the speed action. The steering angles are discretized into bins of
$25^{\circ}$ with a maximum steering angle $\alpha_{\text{max}}=50^{\circ}$ in
both directions. The set of all possible steering directions is
$\text{Angles}=\\{-50^{\circ},-25^{\circ},0^{\circ},25^{\circ},50^{\circ}\\}$.
The car can choose between three distinct speed actions:
$\text{SpeedActions}=\\{\text{accelerate, maintain, decelerate}\\}$. The
accelerate action corresponds to an increase in speed by $5$ kmph, the
decelerate action corresponds to a decrease in speed by $5$ kmph, and the
maintain action corresponds to no change in speed.

$T$: Represents the transition probability,
$T(s_{t},a_{t},s_{t+1})=p(s_{t+1}|s_{t},a_{t})\in[0,1]$, which defines the
likelihood of transitioning from state $s_{t}\in S$ to state $s_{t+1}\in S$
when taking action $a_{t}\in A$ at time $t$. These transitions are fully
determined by car movement kinematics and the pedestrian model.

$Z$: Signifies the set of observations,
$\\{\\{[c,ped_{1}^{o},ped_{2}^{o},...,ped_{n}^{0}]\\}\\}$, containing
information about the car’s state and the observable aspects of pedestrians in
the scene.

$O$: Denotes the observation probability,
$O(s_{t+1},a_{t},o_{t+1})=p(o_{t+1}|s_{t+1},a_{t})\in[0,1]$, which represents
the likelihood of observing $o_{t+1}\in Z$ when transitioning to $s_{t+1}$
after executing action $a_{t}$.

$R$: Stands for immediate rewards, $R(s_{t},a_{t})\in\mathbb{R}$, for
executing action $a_{t}$ in state $s_{t}$. The reward function is formally
defined in Definition 2

$\gamma$: Represents the discount factor within the range $[0,1]$, and we set
$\gamma=0.99$.

###  3.3 Classical Baseline NavA2C

In this section, we describe NavA2C, a DRL-based architecture that will serve
as a baseline for comparison with our proposed quantum-supported method,
Nav-Q.

NavA2C, inspired by A2C-CADRL-p [5], combines a symbolic path planner [4] and
a modified A2C [12] agent, such that the DRL agent is only responsible for the
speed action. The architecture is shown in Figure 1.

Figure 1: NavA2C architecture

The input for the DRL agent is the car intention $I$ (Figure 2) which is the
semantic segmentation of the environment from a bird eye view overlayed with
the planned and traveled path. The DRL agent outputs the speed action
$acc_{t}$ at every time step using car intention $I$ along with the reward
$R_{t}$, car’s velocity $v_{t}^{c}$, and car’s speed action in the previous
time step $acc_{t-1}$. The steering action $\alpha_{t}$, needed to control the
car’s lateral trajectory, is derived from the path calculated by the Anytime
Weighted Hybrid A* Path Planner at every time step. The speed action $acc_{t}$
together with the steering angle $\alpha_{t}$ is passed on to CARLA simulator
as a tuple $a_{t}=(acc_{t},\alpha_{t})$ which serves as the control signal for
the car simulated in the CARLA environment.

Figure 2: Car Intention $I\in\mathbb{R}^{400\times 400\times 3}$ is the
semantic segmentation of the bird eye view of the environment. The white
dotted line represents the planned path while the black dotted line represents
the path already traveled by the car.

The DRL agent in NavA2C consists of four main components: Feature Encoder
$E_{\psi}$, Actor $\pi_{\theta}$, LSTM, and Critic $V_{\phi}$. $E_{\psi}$ is
responsible for learning a low-dimensional representation of car intention $I$
using a long sequence of CNN layers. The output of the feature encoder,
$E_{\psi}(I)$, is concatenated with the reward $R_{t}\in\mathbb{R}$, the car’s
velocity $v_{t}\in\mathbb{R}^{2}$, and the car’s speed action in the previous
step $acc_{t-1}\in\mathbb{R}$. This concatenated information is passed as
input to the LSTM. The LSTM’s hidden state $h_{t}$ is then passed to the actor
and critic networks to determine $\pi_{\theta}(a_{t}|h_{t},o_{t})$ and
$V_{\phi}(h_{t},o_{t})$, respectively.

The Actor ($\pi_{\theta}$) is implemented through a dense neural network. It
takes input $h_{t}$ and produces a $3$-dim vector with associated
probabilities for speed actions (accelerate, maintain, and decelerate). The
critic $V_{\phi}$ is also implemented using a dense neural network and
evaluates the actions chosen by the actor by estimating the expected
cumulative reward associated with a given state-action pair. By leveraging
these evaluations, the actor adjusts its policy to prioritize actions with
higher rewards.

Specifically, the outputs of the actor and critic are the two components that
allow the calculation of the loss function during training, defined as
follows.

######  Definition 1 (NavA2C Loss Function).

Given the observation $o_{t}$, action $a_{t}$, value function $V_{\phi}$ with
parameters $\phi$, and actor policy function $\pi_{\theta}$ with parameters
$\theta$, the loss functions to train parameters $\phi$ and $\theta$ are given
by,

$\displaystyle J_{V}(\phi)=(G_{t}-V_{\phi}(h_{t},o_{t}))^{2}$ (1)
$\displaystyle
J_{\pi}(\theta)=\log(\pi_{\theta}(a_{t}|h_{t},o_{t}))\cdot(G_{t}-V_{\phi}(h_{t},o_{t}))+\beta
H(\pi_{\theta}(a_{t}|h_{t},o_{t}))$ (2)

where $\beta$ is a hyperparameter that controls the weight of the entropy
term, $G_{t}$ is the total discounted reward, and

$\displaystyle
H(\pi_{\theta}(a_{t}|h_{t},o_{t}))=\sum_{a_{t}\in\mathcal{A}}\pi_{\theta}(a_{t}|h_{t},o_{t})\cdot\log(\pi_{\theta}(a_{t}|h_{t},o_{t}))$
(3)

is the entropy of the actor policy.

Importantly, the critic is utilized in calculating the loss function during
training, providing feedback on the quality of selected actions. Its use is
not required at the time of testing. Nevertheless, opting for a critic with
limited expressive power may pose challenges in capturing complex
relationships, leading to slow learning, and difficulties in generalization
and stability. To address these issues, selecting a critic with ample capacity
to represent environmental intricacies, through advanced models, is crucial.
Thus, the primary distinction between the training architecture depicted in
Figure 1 and the corresponding testing architecture lies in the absence of the
critic.

Another crucial aspect is the design of an effective reward function, as it
directly impacts the learning process and the behavior of the autonomous
vehicle. In fact, a meticulously crafted reward function must align the
learning objectives with the desired behavior, contributing to the development
of a reliable and safe autonomous driving system. Drawing inspiration from
prior works [14, 5], we define the following reward function for NavA2C.

######  Definition 2 (NavA2C Reward).

Given the current state $s_{t}\in S$ and previous action
$a_{t-1}\in\mathbb{A}$, the reward $R_{t}(s_{t},a_{t-1})$ is,

$R_{t}(s_{t},a_{t-1})=\begin{cases}r_{\text{goal\\_reached}}=+200&\begin{aligned}
&\text{for reaching goal position, i.e., }\\\
&p_{c}(t)=p_{c}^{\text{goal}}\end{aligned}\\\ \hline\cr
r_{\text{hit}}=-100*\beta&\begin{aligned} &\text{For colliding with the
obstacles }\\\ &\text{(pedestrian, cars, etc.) }\beta\text{ is
proportional}\\\ &\text{to the impact speed}\end{aligned}\\\ \hline\cr
r_{\text{obstacle}}=-obstacleCost&\begin{aligned} &\text{Penalty if there is a
pedestrian or cars }\\\ &\text{ in the hit area and }v_{t}^{c}\neq 0\\\
\end{aligned}\\\ \hline\cr r_{\text{near\\_miss}}=-10&\begin{aligned}
&\text{If there is a pedestrian in the near-miss }\\\ &\text{ area of
car}\end{aligned}\\\ \hline\cr r_{\text{over\\_speeding}}=-10&\begin{aligned}
&\text{For crossing the maximum speed limit of}\\\ &50\text{
kmph}\end{aligned}\\\ \hline\cr
r_{\text{not\\_goal}}=-goal\\_dist/1000&\begin{aligned} &\text{Dynamic penalty
based on distance }\\\ &\text{from goal}\\\ \end{aligned}\\\ \hline\cr
r_{\text{braking}}=-1&\begin{aligned} &\text{Penalty if the car brakes when
it’s not }\\\ &\text{ moving}\\\ \end{aligned}\\\ \hline\cr
r_{\text{steer}}=-1&\begin{aligned} &\text{Penalty if }\alpha_{t}\neq 0\\\
\end{aligned}\\\ \end{cases}$

One drawback of NavA2C [5] is the consistent acceleration during the test
phase when actions are determined deterministically. To address this issue, we
mitigated $r_{goal\\_reached}$ and introduced a penalty for overspeeding,
denoted as $r_{over\\_speeding}$. Drawing inspiration from HyLEAR [5], we
incorporated $r_{near\\_miss}$ into the reward function to penalize near
misses, encouraging the car to maintain a safe distance from pedestrians.
Additionally, $r_{hit}$ penalizes crashes or collisions with pedestrians,
promoting the safety of the autonomous car. The term $r_{obstacle}$ is
designed to encourage the autonomous car to avoid collisions with other
obstacles. Furthermore, $r_{steer}$ promotes comfortable and smoother
navigation by penalizing the agent for choosing actions that necessitate
excessive steering. Finally, $r_{not\\_goal}$ incentivizes reaching the goal
more expeditiously.

##  4 Methods

In this section, we introduce Nav-Q, the first quantum-supported deep
reinforcement learning architecture that combines classical and quantum neural
networks to effectively train a reinforcement learning agent for safe
navigation of self-driving cars. Nav-Q is primarily based on an actor-critic
model, wherein the critic component is realized through a parameterized
quantum circuit and a fully connected classical layer. This design enables us
to harness the capabilities of a quantum algorithm exclusively during the
training phase, eliminating the need for a QPU in the vehicle during testing.

Additionally, we introduce a novel quantum embedding technique that extends
the Data Reuploading strategy to efficiently encode high-dimensional vectors
using an arbitrary number of available qubits.

###  4.1 Nav-Q Architecture

Nav-Q is inspired by NavA2C (Section 3.3), which comprises two major
components: an Anytime Weighted Hybrid A* Path Planner [4], determining the
steering angle for the car, and DRL components—a hybrid actor-critic model
responsible for determining speed actions (accelerate, maintain, decelerate).
The objective is to reach the destination in the shortest time possible while
avoiding collisions with other agents that may be present in the scene (such
as other cars, pedestrians, etc.).

To be able to generalize any possible scenario that the car might encounter,
the DRL agent needs to be trained for thousands of episodes, which implies
running the training procedure for several days even when considering a
limited set of scenarios. Furthermore, DRL algorithms are very unstable with
respect to weight initialization, which means that it is necessary to run the
training procedure several times with different initial parameters to achieve
reliable performance in terms of driving policies.

The idea of Nav-Q is to introduce a quantum component into the DRL agent of
NavA2C to obtain a quantum-supported architecture that can improve classical
performance in terms of trainability and/or stability while having (at least)
the same performance in terms of learned policy (time-to-goal, number of
crashes, etc.). Also, the quantum component has not to be included at the time
of testing, since this would require placing a QPU in the car, and invalidate
the practical use of the proposed methods.

Figure 3: Quantum-supported Deep Reinforcement Learning agent in Nav-Q. In
contrast to the complete architecture of NavA2C illustrated in Figure 1, this
depiction focuses solely on the DRL agent. The primary distinction from the
classical model lies in the DRL agent’s critic, which is replaced by a hybrid
quantum-classical algorithm. Its design is essential for training and
evaluating the loss function.

To fulfill these requirements, Nav-Q introduces a parametrized quantum circuit
to implement the critic within the actor-critic framework. This strategic
choice allows us to exclusively employ the quantum algorithm during the
training phase, where the critic evaluates the policy selected by the actor.
In contrast, during the testing phase, only the actor is utilized, as it
produces the action. Therefore, the training process, recognized as the most
challenging aspect of RL, is where the introduction of quantum components is
expected to have the maximum impact.

The quantum-supported DRL agent of Nav-Q is visually represented in Figure 3.

As for NavA2C, the Nav-Q agent comprises four main components: Feature Encoder
$E_{\psi}$, Actor $\pi_{\theta}$, LSTM, and Critic $V_{\phi}$. $E_{\psi}$ is
responsible for learning a low-dimensional representation of car intention
$I$, using a long sequence of CNN layers. The output of the feature encoder,
$E_{\psi}(I)$ is concatenated with the reward $R_{t}\in\mathbb{R}$, the car’s
velocity $v_{t}\in\mathbb{R}^{2}$, and the car’s speed action in the previous
step $acc_{t-1}\in\mathbb{R}$ and passed as input to the LSTM (See Figure 3).
The LSTM, stores in its hidden state a more compressed representation of past
observations and current input. It encodes information about the previous
states that the agent has encountered, helping to infer the current state even
when the observations are noisy and incomplete. The LSTM’s hidden state
$h_{t}$ is then passed to the actor and critic networks to determine
$\pi_{\theta}(a_{t}|h_{t},o_{t})$ and $V_{\phi}(h_{t},o_{t})$ respectively.
Recall that the Value function $V_{\phi}(h_{t},o_{t})$ implemented using the
critic network gives the expected return if one starts in state $s$ and always
acts according to policy $\pi_{\theta}$. The Actor ($\pi_{\theta}$) in Nav-Q
is implemented through a dense neural network and is the same as to NavA2C. It
takes input $h_{t}$ from the LSTM layer and produces a $3$-dim vector with
associated probabilities for speed actions (accelerate, maintain, and
decelerate) during training.

The implementation of the critic constitutes a key distinction compared to
NavA2C and, more broadly, to all classical actor-critic approaches.

###  4.2 Hybrid Quantum-Classical Critic

The critic $V_{\phi}(h_{t},o_{t})$ in Nav-Q is realized through a hybrid
quantum-classical algorithm made up of two components. The first one is a PQC
which processes $h_{t}$ \- the hidden state of the LSTM - through unitary
operations to generate a parametrized quantum embedding in the Hilbert space.
The quantum embedding is then converted into an $n$-dimensional classical
vector (where $n$ is the number of qubits of the quantum circuit) using the
expectation measurement of Pauli-$Z$ observables for each single qubit. At
this point, there is a mismatch between the output of PQC ($\mathbb{R}^{n}$)
and the required dimension of the Value function
$(V_{\phi}(h_{t},o_{t})\in\mathbb{R}$). Thus, to map the $n$-dim vector
resulting from the PQC to a single value of $V_{\phi}$, the second part of the
critic is implemented, which is essentially a fully connected (FC) neural
network layer made up of $n$ input and one output nodes (no hidden layers).

Despite the reduction in problem dimensionality given by the combination of
the feature encoder and the LSTM, the complexity of solving real-world issues,
such as the CFN, poses a challenge in terms of data encoding within a
parametrized quantum circuit. To tackle this challenge, we propose the Qubit
Independent Data Encoding & Processing (QIDEP) strategy, which enables the
encoding of a high-dimensional vector using an arbitrary number of qubits.

Note that the utilization of $\theta$ parameters for the actor and $\phi$
parameters for the critic aligns with established RL literature on actor-
critic approaches. However, starting from the next section, we employ the
parameters $\theta$ to denote the trainable parameters of the quantum circuit
implementing the critic to be consistent with quantum computing literature.

###  4.3 Qubit Independent Data Encoding & Processing

Data reuploading [11] is an efficient strategy for quantum embedding which
allows the approximation of any continuous function using a single-qubit
circuit. We extend this idea to propose a novel strategy, named Qubit
Independent Data Encoding and Processing (QIDEP), where a multi-qubit system
allows encoding a high-dimensional vector using a flexible number of qubits. A
formal definition of this strategy is given in Definition 3.

Figure 4: Graphical representation of the sublayer concept in QIDEP,
comprising $U_{in}(x)$ and $U(\theta)$. The quantum gates of $U_{in}(x)$ for
data encoding are illustrated in green, while the ansatz $U(\theta)$ with
trainable parameters is depicted in blue. In this example, the $U(\theta)$
structure adopts a hardware-efficient architecture, consisting of
parameterized $R_{y}$ and $R_{z}$ gates, followed by a daisy chain of CZ
gates. On the other hand, the quantum gates of $U_{in}$ align with those
proposed in the classical Data Reuploading technique [11] consisting of a
sequence of the three Pauli rotation gates, whose parameters are non-trainable
and depend on the input feature $x$.

######  Definition 3 (Qubit Independent Data Encoding & Processing).

Let $x\in\mathbb{R}^{p}$ be the input classical data, $U(\theta)$ be a
parameterized quantum circuit with trainable parameters $\theta$, $U_{in}(x)$
be the unitary for data encoding based on Angle Encoding, $n$ be the desired
number of qubits and $L\in\mathbb{N}$ be the desired number of layers in the
quantum circuit. In QIDEP, each layer $U_{l}$ can be written as a composition
of sublayers $S_{m}^{l}$

$\displaystyle U_{l}=\prod^{m=1}_{m=k}S_{m}^{l}$ (4)

where $S_{m}^{l}$ is the $m$-th sublayer of the $l$-th layer defined as
$S_{m}^{l}=U(\theta_{m}^{l})U_{in}(x^{m})$, with
$x^{m}=\\{x_{3n(m-1)+1},\dots,x_{3nm}\\}$ indicating a specific subset of
elements in the input feature $x$. Note that the number of sublayers
$k=\lceil\frac{p}{3n}\rceil$ is fixed and given the input feature and the
number of qubits, the vector must be padded with a zero vector of length
$3nk-p$.

Importantly, the architecture allows to freely choose the number of layers, as
well as the number of trainable parameters within each sublayer, depending on
the task at hand. Thus, a $L$-layered, $n$-qubit QIDEP quantum circuit that
has to process a $p$-dimensional vector can be written as:

$\displaystyle
U(\theta,x)=\prod^{l=1}_{L}\prod^{m=1}_{m=k}U\left(\theta_{m}^{l}\right)U_{in}\left(x^{m}\right)$
(5)

An example of QIDEP strategy is shown in Figure 5. In Data Reuploading [11],
each layer can be seen as a single unit of $U_{in}$ and $U(\theta)$, and the
number of layers in the circuit is considered a hyperparameter (as in
classical neural networks). In QIDEP, we introduce the concept of sublayer
$S$. Specifically, each layer $l$ consists of $k$ sublayers ${S^{l}_{m}}$,
each comprising unitaries $U_{in}(x)$ and $U(\theta)$. Here, $U_{in}(x)$ is
employed to encode a contiguous sub-sequence of features of $x$, while
$U(\theta)$ represents the parametrized ansatz. Figure 4 shows an example of a
sublayer considering a 4-qubit circuit and a hardware efficient [24]
parametrized ansatz.

Figure 5: Example of a quantum circuit implementing the QIDEP strategy to
encode a $24$-dimensional vector using $4$ qubits and $3$ layers. The quantum
circuit is segmented into layers, each containing identical quantum gates but
varying parameters within each ansatz. Each layer comprises sublayers
$S^{l}_{m}$, which, in turn, includes a data encoding gate, $U_{in}(x)$, and
the ansatz, $U(\theta)$. The grey boxes represent the layers, the red dotted
rectangles symbolize sublayers, the green boxes denote the data encoding
module $U_{in}$, and the blue boxes represent the ansatz $U(\theta)$. Notice
that the additional classical fully connected layer connected to the
measurements of the $4$ qubits is not part of the specific QIDEP design but
rather a component of the Nav-Q architecture.

Specifically for the Nav-Q architecture, the dimensionality reduction task is
implemented through a Fully Connected (FC) layer [7, 19]. Incorporating an FC
layer for dimensionality reduction helps scale the output of the PQC using
trainable weights, enabling the critic to achieve a Value function output that
aligns more closely with the range of the true Value function. Additionally, a
trainable output range can enhance convergence and reduce sensitivity to the
choice of hyperparameters and random initialization of model parameters [9].

As a result, the second part of the critic is implemented using an $n\times 1$
FC neural network layer. This layer processes the $n$-dimensional vector,
generating a single number that represents the Value for the observation
$o_{t}$. An $n\times 1$ FC layer involves a total of $n+1$ trainable
parameters—$n$ weights and $1$ bias.

##  5 Performance Evaluation

In this section, we assess Nav-Q using the CARLA-CTS benchmark, a widely
recognized virtual environment for evaluating the performance of DRL models in
the context of self-driving cars. Additionally, we compare the results of
Nav-Q with those of its classical baseline, NavA2C, which relies solely on
conventional computational resources. Finally, we train Nav-Q on a simulated
noisy quantum system with the parameter-shift rule to estimate the expected
performance on real quantum hardware.

###  5.1 Experimental Settings

#### Environment

For comparative experimental evaluation of CFN methods of self-driving cars in
critical traffic scenarios, we use the virtual CARLA-CTS benchmark [5], an
extension of OpenDS-CTS [4] for the driving simulator CARLA [25]. This
benchmark contains about thirty-thousand scenes of twelve scenarios mainly
based on the GIDAS [26] study of road accidents with pedestrians in Germany
and simulated in CARLA on a test drive of about 100 meters. In Figure 6, the
blue boxes with solid arrows denote autonomous car movements, the red boxes
with solid arrows denote static or dynamic obstacles such as parking or
incoming cars, and the dotted arrows denote the pedestrian movement.

Since Nav-Q is trained using quantum simulations, the training time is
considerably high, thus to to reduce the complexity of the tested environment,
we adopt as training scenarios 1, 3, 4, 5, 6, and 8 and test our model on all
scenarios from 1-8. A scene is represented by a 6-tuple
$(\text{scenario},p^{c}_{\text{start}},p^{c}_{goal},\theta^{c}_{\text{start}},P,C)$,
where $\text{scenario}\in\text{Scenarios}$ correspond to the scenario being
simulated in the scene, $p^{c}_{\text{start}}\in\mathbb{R}^{2}$ denotes the
starting position of the car, $\theta^{c}_{\text{start}}\in\mathbb{R}^{2}$
represents the starting orientation of the car,
$p^{c}_{goal}\in\mathbb{R}^{2}$ indicates the goal position of the car, $P$ is
the set of pedestrians in the environment and $C$ is the set of cars in the
environment apart from the autonomous car $c$. Each scene is essentially an
instantiation of a particular scenario with a specific configuration for
pedestrian spawn point and pedestrian speed. For training, we consider
pedestrian speed in the range of $0.6-2.0$ m/s with a step size of $0.1$ and
pedestrian distance from $0-40$ m with a step size of $1$. For testing, we
consider pedestrian speed in the $0.25-2.85$ m/s range and pedestrian distance
in the $4.75-49.25$ m range. As a result, there were $3690$ scenes in the
training set and $9936$ scenes in the test set.

Figure 6: Accident scenarios on the basis of GIDAS [26] study. The autonomous
vehicle is represented by the solid lines, stationary objects that block its
view are represented by the red squares, and pedestrian movement is
represented by the dotted lines. Scenario id is represented by the numbers at
the bottom of each scenario.

#### Classical Baseline

In this study, we evaluate the performance of Nav-Q in comparison to its
classical counterpart, NavA2C, which draws inspiration from A2C-CADRL-p [5]
(Section 3.3). Notably, we introduce several enhancements that aim to improve
its performance compared to earlier iterations.

One key modification involves the incorporation of layer normalization [27]
into the neural network architecture of the Feature Encoder ($E_{\psi}$),
Actor ($\pi_{\theta}$), and Critic ($V_{\phi}$). This addition was absent in
the original A2C-CADRL-p model [5]. The inclusion of layer normalization is
intended to promote more stable and expedited training. Furthermore, in the
initial version of A2C-CADRL-p, the LSTM produced a 256-dimensional vector
($h_{t}\in\mathbb{R}^{256}$). Given the challenges of encoding such high-
dimensional vectors into a quantum state, we made adjustments to $E_{\psi}$
and LSTM to produce a 32-dimensional vector instead. Additionally, we fine-
tuned the reward function to facilitate more consistent and stable learning
(See Section 3.3).

It is worth noting that, in the realm of CFN for self-driving cars, our study
is pioneering in its investigation of hybrid quantum-classical reinforcement
learning algorithms. As a result, there are no quantum baselines to compare
with, as we are the first to delve into this domain.

#### Implementation

To implement the parametrized quantum circuit in the critic of Nav-Q, we
conducted experiments using 4 and 6 qubits, varying the number of layers from
1 to 3. To select the best quantum model, we trained different configurations
for up to 10,000 episodes and chose the configuration that yielded the best
results in terms of policy improvement. Once the best quantum model was
identified, we trained Nav-Q and NavA2C for 10,000 episodes to assess the
performance in terms of training policy of both approaches. To evaluate
convergence rate and training stability we run six different weight
initializations of the overall architecture, training for up to $5,000$
episodes, and analyzing the average training behavior.

For both NavA2C and Nav-Q, gradients were computed after each episode, and the
network weights were updated using the Adam optimizer with a learning rate of
$0.0005$. Each episode had a maximum duration of $500$ time steps and ended
prematurely if the car reached its goal or collided with any obstacle. Given
the challenge of encoding high-dimensional classical data into a quantum
state, we set the output of the LSTM layer for both Nav-Q and NavA2C to
produce $h_{t}\in\mathbb{R}^{32}$, which was initially a $256$-dimensional
vector in A2C-CADRL-p [5] (the inspiration for NavA2C).

In the case of Nav-Q, we utilized the ‘default.qubit’ device of PennyLane for
quantum simulation and employed backpropagation with gradient descent to
update the weights of the entire model. It’s important to note that using
backpropagation for training quantum circuits would not be feasible on quantum
hardware [28, 29]. To estimate the performance as if we had a real quantum
device, we also trained Nav-Q using the parameter-shift rule [28], an
alternative method to compute partial derivatives of quantum expectation
values with respect to gate parameters on quantum hardware. Nevertheless,
gradient calculation through the parameter-shift rule is computationally
expensive. To address this, we reduced the dimension of the LSTM output from
$32$ to $6$ (i.e., $h_{t}\in\mathbb{R}^{32}$) and trained a circuit with only
$2$ qubits and $1$ layer to reduce circuit depth. We also simplified the
learning task by training on only the first scenario of the CARLA-CTS 1.0
benchmark for $2,500$ episodes.

Finally, we also trained and tested the simplified version of Nav-Q under two
simulated noise models, Quantum Gate Error [30] and Depolarising Error [31].
To simulate Quantum Gate Error, we add uniform random noise to the parameters
of rotation gates such that
$\theta\leftarrow\theta+0.01\times\theta\times\delta$, where
$\delta\sim\text{Uniform}(0,1)$. This kind of error arises due to imperfection
in the realization of rotation gates on quantum hardware. Depolarising Error
represents a random error in between each operation on a qubit. These errors
are injected in the form of bit-flips (x error), phase-flips (z error), or
both at the same time (y error). We use the in-built library of Pennylane [18]
to simulate this error.

#### Metrics

To assess the performance Nav-Q with the classical baselines, we define three
categories of metrics:

  1. 1.

Trainability: This aspect refers to the capacity of an RL model to be
effectively trained to perform a specific task or acquire a particular
behavior within the environment. A conventional method for evaluating
trainability involves analyzing the Return vs. Episodes curve, illustrating
the smoothed cumulative reward (i.e., return) as the number of episodes
increases. Specifically, we assess the mean and standard deviation of the
corresponding Area Under the Curve (AUC) [8, 9] to comparatively evaluate the
overall convergence rate and stability across various initializations of the
overall architecture.

  2. 2.

Driving Policy: The performance of each method in terms of driving policy is
measured using the following metrics: (a) the overall safety index (SI)
defined as total number of scenarios in which the method is below given
percentages of crashes and near-misses; (b) the crash and near-miss rates (%),
and time to goal (TTG) in seconds [5].

  3. 3.

Learnability: To methodologically assess the ability of both quantum and
classical models to learn complex and diverse functions beyond the immediate
problem statement, we employ the calculation of the effective dimension [32,
33]. This complexity measure, rooted in information geometry, estimates the
size of the space containing all possible functions for a particular model
class, utilizing the Fisher information matrix (FIM) as the metric. Moreover,
the spectral analysis of the FIM enables the examination of the curvature of
loss surfaces, providing insights into the nature of loss surfaces for both
classical and quantum models [33]. Indeed, the shape of the optimization
landscape plays a crucial role in understanding whether a specific model can
effectively find a suitable solution to the problem.

###  5.2 Results

#### Trainability

To choose the optimal architecture for Nav-Q and compare it with the classical
baseline, we ran various configurations of the PQC for the critic, varying the
number of qubits and layers and assessed the convergence rate and stability in
terms of the Return vs. Episode curve. Results are shown in Figure 7.

|
---|---
Figure 7: Return vs. Episodes smoothed curves of Nav-Q with a 4-qubit (left)
and 6-qubit (right) parametrized quantum circuit and number of layers ranging
from $1$ to $3$.

We observe that, in all cases, the model converges after 10,000 episodes,
yielding comparable return, despite having varying numbers of parameters. This
aligns with a well-known observation in the classical domain: an increase in
the model’s complexity does not necessarily guarantee a performance
improvement. However, when using a 6-qubit critic, training performance
becomes unstable, with a sudden drop in cumulative reward (return) requiring
hundreds of episodes to recover an increasing trend. This instability is not
observed with a 4-qubit circuit using one or two layers. The behavior can be
attributed to a high number of parameters leading to optimization issues
arising from a complex landscape, potentially affected by barren plateaus.
Table 2 presents a comparison of training times and the number of parameters
for various configurations of Nav-Q. The training times show an increase with
the number of qubits and layers, posing a significant challenge and extending
to several days for each model. Nevertheless, when addressing real-world
problems, such as the CFN benchmarked on standard classical data, testing a
quantum-supported model remains feasible, albeit challenging.

Method | #qubits | #layers |  |  #parameters ($d$)
---
| Training Time
---
(days)
Nav-Q | 4 | 1 | 29 | 6.8
2 | 53 | 10.87
3 | 77 | 14.64
6 | 1 | 31 | 8.14
2 | 55 | 11.74
3 | 79 | 18.46
|  |  |  |
Table 2: Training times and number of parameters for different critic
architectures of Nav-Q.

Considering the comparable results of the 4-qubit architecture, particularly
when focusing on configurations with only one or two layers, the key
consideration becomes the stability of the model in choosing the optimal
architecture. In this respect, we conducted an analysis using five different
weight initializations. The results, encompassing mean, standard deviation,
and range, are illustrated in Figure 8. This choice is motivated by the
imperative to reduce training times, as emphasized in Table 2, where each
experiment demands several days for a single training session to be completed.

Figure 8: Comparison of Return vs. Episodes graph of two different 4-qubit
Nav-Q architectures with 1 and 2 layers respectively, executed for six
different parameters initializations.

Despite the similarity in average performance in terms of return for both
architectures, we observe that the 1-layer model exhibits less stability
compared to its 2-layer counterpart. Given that stability, along with average
reward, is a crucial factor in analyzing reinforcement learning performance,
we choose the critic with a parameterized quantum circuit using 4 qubits and 2
layers as the best model.

Figure 9: Comparison of Return vs. Episodes graph of NavA2C and Nav-Q with 4
qubits and 2 layers.

The next step is the comparison of the best configuration of Nav-Q with its
classical counterpart NavA2C. In particular, we trained NavA2C for $10,000$
episodes and compared it with Nav-Q. Results are shown in Figure 9.

Nav-Q exhibits a superior convergence rate in the initial $4,000$ episodes,
indicating that a DRL agent with an enhanced quantum critic demonstrates
faster trainability compared to the classical counterpart. However, over an
extended duration, the two models attain similar performance. To better assess
the convergence rate and the training stability, we conducted six training
sessions each with distinct initialization weights. This experiment aims to
evaluate two critical aspects: the average convergence rate (performance
improvement as the number of episodes increases) and stability (sensitivity of
the two models to different weight initializations of the neural networks,
both classical and quantum). Results are shown in Figure 10. The trend of the
curves remains consistent for both quantum and classical models, suggesting
similar overall performance in terms of driving policy, as evidenced by the
resemblance in average rewards between the two approaches. However, the Nav-Q
return is mostly higher than NavA2C, albeit to a lesser extent than in the
previous case.

To quantitatively evaluate convergence and stability, we calculate the average
and standard deviation of the AUC of the Return vs. Episode curve across the
six runs. A higher average AUC implies better convergence, while a lower
standard deviation indicates enhanced stability.

Nav-Q reports a higher average AUC ($2440.6$) than NavA2C ($2362.95$). Upon
examining the standard deviation, Nav-Q demonstrates lower variability
$(758.78)$ compared to NavA2C $(902.73)$, which implies better stability of
the quantum model with respect to its classical counterpart.

Figure 10: Comparison of the smoothed Reward vs. Episodes curves for Nav-Q
with $4$ qubits and $2$ layers, and NavA2C averaged over multiple runs. The
red-colored plots in the graph correspond to Nav-Q while the blue colored
plots refer to NavA2C. The thick solid line represents the mean of $6$ runs,
each with a different weight initialization of the overall architecture. The
colored shaded area represents the standard deviation and the thin dotted line
represents the maximum and minimum return values.

#### Driving Policy

Starting with the two models trained for $10,000$ episodes (Figure 9), we
evaluated the performance in terms of driving policy. Results are shown in
Table 3.

Method |  | #para-
---
meters
| Time
---
to
goal
(s)
| crashes
---
(%)
| near-
---
misses
(%)
| Safety
---
Index
(SI)
| Mean
---
Return
| Training Time
---
(days)
Nav-Q | 53 | 11.74 | 13.23 | 23.62 | 3 | 0.10 | 10.87
NavA2C | 2305 | 11.77 | 12.47 | 22.39 | 3 | 0.12 | 2.7
|  |  |  |  |  |  |
Table 3: Comparison of driving policy of NavA2C and Nav-Q with 4 qubits and 2
layers after 10,000 episodes of training.

Both approaches seemed to have learned a similar policy. Nav-Q has a slightly
lesser mean time to goal compared to NavA2C, which implies that the model
trained using a quantum critic reaches the goal faster compared to the fully
classical approach. When looking at collisions (crashes and near-misses), the
classical approach slightly outperforms Nav-Q, providing a lower percentage
for crashes and near-misses. However, the SI -defined in the range $[1,8]$
that quantifies the total number of scenarios in which the agent exhibits the
number of crashes and near misses below $20\%$\- is the same. In general, the
differences in terms of driving policy seem to be not very significant when
comparing Nav-Q with NavA2C. This implies that the advantages provided by
Nav-Q in terms of convergence rate and stability come without affecting the
performance when considering the behavior of the car during the test phase.

Finally, the last column of Table 3 reports the number of days required to
train the two models. As observed, while the quantum-supported architecture
reduces complexity in terms of the number of parameters, the training times
are notably longer. This suggests that the current optimization strategy,
which includes the forward pass—where it is necessary to simulate the full
quantum circuit after each update—and standard backpropagation, which is
usually well-suited for classical neural networks, might require custom
amendments to perform optimally when dealing with quantum-supported solutions
on real-world data.

#### Learnability

The normalized effective dimension (ED) [33], denoted by
$\overline{d}{\gamma,n}=\frac{d{\gamma,n}}{d}$ provides the proportion of
active parameters relative to the total number of parameters in the model. A
high normalized effective dimension suggests that the model is utilizing a
substantial portion of the model space, with many parameters actively involved
in fitting the data. Conversely, a low effective dimension indicates that the
model is using only a limited part of the model space, with a smaller
proportion of parameters actively contributing to the model’s performance.
Results comparing Nav-Q and NavA2C in terms of ED are shown in Table 4.

Method | #qubits | #layers |  |  #parameters ($d$)
---
ED ($d_{\gamma,n}$) |  | Normalized ED
---
$\overline{d}_{\gamma,n}=\frac{d_{\gamma,n}}{d}$
Nav-Q | 4 | 1 | 29 | 8.14 | 0.28
4 | 2 | 53 | 10.79 | 0.20
4 | 3 | 77 | 13.30 | 0.17
6 | 1 | 31 | 6.76 | 0.22
6 | 2 | 55 | 9.11 | 0.17
6 | 3 | 79 | 12.97 | 0.16
NavA2C | NA | NA | 2305 | 56.65 | 0.02
|  |  |  |  |
Table 4: Comparison of all the configurations tested for Nav-Q and NavA2C in
terms of the number of parameters, and the effective dimension.

We observed that $\overline{d}_{\gamma,n}$ for all circuits of Nav-Q is higher
than NavA2C. This implies that the quantum critic has a greater capacity to
model complex functions compared to the classical critic. Understanding the
capacity of a quantum model can be advantageous as it provides insight into
the model’s capability to learn patterns even before training, which is a
resource-intensive task.

In addition, we analyze the eigenspectrum of the FIM to gain insights on the
shape of the optimization landscape. Figure 11 shows the eigenvalue
distribution of FIM obtained for the critics of Nav-Q and NavA2C.

We arrange the eigenvalues in descending order and plot the top $50$
eigenvalues for both cases. The subplots provide a closer examination of the
distribution of eigenvalues that are close to zero. In the case of NavA2C, a
few exceptionally high eigenvalues are observed, with the majority clustering
near zero. This suggests that the loss curvature is steep along the
eigenvector corresponding to the highest eigenvalue. Given that most
eigenvalues are close to zero, we can infer that the loss surface is primarily
flat, featuring minor ridges and valleys.

For Nav-Q, similar to NavA2C, a single prominent eigenvalue is noticeable,
with the majority of the eigenvalues clustered close to zero. This phenomenon
results in extremely small gradients, thereby slowing down optimization via
gradient descent. This issue resembles the vanishing and exploding gradient
problem encountered in classical neural networks.

This observation diverges from the findings in [33], where it is claimed that
the eigenvalues in the case of PQCs should be more evenly spread. We speculate
that the anomaly may be attributed to the benchmark design. However, we
acknowledge that further investigation is required to fully understand this
aspect.

NavA2C Nav-Q

---

---

Figure 11: Eigenvalue distribution of Fisher Information Matrix for the critic
of NavA2C (right) and Nav-Q (left).

#### Simulated Noisy Environment and Parameter-Shift Rule

All the previously described experiments utilized classical backpropagation
for optimizing the parameters in Nav-Q. However, this approach is only
feasible when using quantum simulation and would be impractical when dealing
with real quantum devices. Furthermore, real near-term quantum devices are
affected by noise which introduces errors and limits the coherence of quantum
states, impacting the accuracy and reliability of quantum computations. To
assess these two aspects, we conducted training procedures based on the
parameter-shift rule and the introduction of noise. Figure 12 compares the
different approaches using the Return vs. Episodes and Entropy vs. Episodes
curves of NavA2C and Nav-Q.

|
---|---
Figure 12: Training performance in terms of Rewards vs Episodes curve (left)
and Entropy vs Episodes curve (right) with respect to different optimizations
settings. In both graphs, we present the results for four different
approaches: NavA2C represents the classical baseline, while two variants of
Nav-Q are depicted depending on the optimization strategy adopted, classical
backpropagation or parameter-shift rule. Additionally, one Nav-Q variant is
trained with different noise models integrated in the circuit simulation, and
the parameter-shift rule is employed for gradient calculation.

Nav-Q trained using backpropagation and NavA2C exhibit similar performance,
consistent with previous experiments. However, when training Nav-Q using the
parameter-shift rule, the convergence rate is considerably slower than with
backpropagation. In this regard, the entropy curve indicates that the
parameter-shift rule is causing the problem of overshooting due to a large
step size, as the entropy curve keeps oscillating around the value of $0.4$.

When introducing noise, we observe a deterioration in the stability of
learning. The convergence rate of Nav-Q trained with the parameter-shift rule
and introducing noise is almost the same as without noise in the initial part
of the training. However, the problem of overshooting for the noisy model
becomes even more pronounced, as evident from its entropy curve. Therefore, we
can conclude that, although the parameter-shift rule enables precise
calculation of the gradient at each iteration on a methodological level, the
performance remains below that of using backpropagation. This could be
attributed to the need to set the magnitude of the gradient shift at each step
in advance. Additionally, as expected, introducing quantum noise leads to a
deterioration in performance in terms of both stability and convergence rate.
Nevertheless, from the Entropy vs. Episodes curve we observe that due to
noise, the RL agent exhibits a higher exploratory nature since the value of
entropy keeps oscillating even after a high number of episodes.

##  6 Discussion and Conclusion

In this work, we introduced Nav-Q, the first quantum-supported Deep
Reinforcement Learning approach designed to address the challenge of
Collision-Free Navigation for self-driving cars. Nav-Q is built on an actor-
critic algorithm to effectively learn an optimal policy for controlling the
speed of self-driving cars. The critic is a hybrid quantum-classical algorithm
constructed using an innovative technique named Qubit Independent Data
Encoding and Processing (QIDEP), allowing the quantum embedding of high-
dimensional classical data without being constrained by the number of qubits.
Consequently, QIDEP provides the flexibility to adapt the number of qubits to
suit specific quantum circuit requirements. Moreover, Nav-Q represents a valid
alternative to existing classical algorithms, as its architecture design
doesn’t require a Quantum Processing Unit at test time, enhancing its
usability for real-world applications.

To the best of our knowledge, Nav-Q is the first proposal of its kind,
introducing a quantum component designed to enhance training performance
without requiring a QPU during testing. This approach can be easily adapted to
address typical problems utilizing the actor-critic model, particularly those
struggling with trainability and stability during the training phase, and can
derive benefits from quantum machine learning models.

We trained Nav-Q using the CARLA-CTS1.0 benchmark [5] and systematically
compared its performance with the classical baseline, NavA2C. In terms of
trainability, the results demonstrated that, on average, Nav-Q exhibited a
superior average convergence rate and better stability compared to NavA2C.
Specifically, when running both approaches with different weight
initializations, Nav-Q demonstrated a higher average AUC of the Return vs
Episodes curves than NavA2C, along with a lower standard deviation, implying
better stability. We believe this is due to the higher number of parameters in
NavA2C than in Nav-Q. Models with more parameters are generally more sensitive
to trainable parameter initialization, as they have a larger space of possible
configurations, making optimization more challenging. Considering the two
models when trained for $10,000$ episodes, we evaluated their performance in
terms of the driving policy of the car. In this regard, Nav-Q and NavA2C
showed similar performance, with Nav-Q tending to achieve the final goal
faster, while NavA2C was slightly better in terms of collision avoidance.

In terms of learnability, Nav-Q exhibited superior performance when
considering the effective dimension and showed similar behavior when examining
the distribution of eigenvalues of the Fisher Information Matrix. In this
context, the quantum model appears to be significantly impacted by the barren
plateau problem, making the optimization procedure challenging in finding a
suitable local minima.

Finally, we conducted smaller-scale training experiments with a $2$-qubit,
$1$-layer Nav-Q using a suitable optimization procedure for real quantum
hardware, known as the parameter-shift rule. We investigated the impact of
noise using two distinct noise models: the Quantum Gate Error [30] and
Depolarising Error [31]. The comparison of the resulting Return vs. Episodes
curves clearly illustrates that the trainability of Nav-Q was adversely
affected by the combination of the parameter-shift rule and noise,
highlighting the challenges posed by these factors on near-term quantum
hardware.

For this reason, a primary challenge to address in the near future is
overcoming the issue of barren plateaus. Various approaches can be considered,
including different parameter initialization techniques [34], layerwise
learning [35], and parameter correlations [36]. Another interesting direction
is to design a Quantum PPO architecture based on the principles of Nav-Q. In
this case, it will be possible to leverage the efficiency of PPO in terms of
more stable learning and faster convergence rate, while facilitating the
training procedure through quantum computation.

Furthermore, a promising avenue involves extending the application of the
Nav-Q architecture to diverse problems beyond the CFN of self-driving cars.
The Nav-Q algorithm can be applied to problems requiring an RL agent
challenging to train using classical neural networks alone. As observed, even
a relatively small quantum circuit possesses greater descriptive power than a
large neural network. Identifying specific applications where training can be
accelerated using quantum computation is crucial for both reinforcement
learning and quantum computing.

## References

  *   * Zhu and Zhao [2021] Zhu, Z., Zhao, H.: A survey of deep rl and il for autonomous driving policy learning. IEEE Transactions on Intelligent Transportation Systems 23(9), 14043–14065 (2021)
  * Chib and Singh [2023] Chib, P.S., Singh, P.: Recent advancements in end-to-end autonomous driving using deep learning: A survey. IEEE Transactions on Intelligent Vehicles, 1–18 (2023) https://doi.org/10.1109/TIV.2023.3318070
  * Kiran et al. [2021] Kiran, B.R., Sobh, I., Talpaert, V., Mannion, P., Al Sallab, A.A., Yogamani, S., Pérez, P.: Deep reinforcement learning for autonomous driving: A survey. IEEE Transactions on Intelligent Transportation Systems 23(6), 4909–4926 (2021)
  * Pusse and Klusch [2019] Pusse, F., Klusch, M.: Hybrid online pomdp planning and deep reinforcement learning for safer self-driving cars. In: 2019 IEEE Intelligent Vehicles Symposium (IV), pp. 1013–1020 (2019). https://doi.org/10.1109/IVS.2019.8814125
  * Gupta and Klusch [2023] Gupta, D., Klusch, M.: Hylear: Hybrid deep reinforcement learning and planning for safe and comfortable automated driving. In: 2023 IEEE Intelligent Vehicles Symposium (IV), pp. 1–8 (2023). https://doi.org/10.1109/IV55152.2023.10186781
  * Jerbi et al. [2021] Jerbi, S., Gyurik, C., Marshall, S., Briegel, H., Dunjko, V.: Parametrized quantum policies for reinforcement learning. Advances in Neural Information Processing Systems 34, 28362–28375 (2021)
  * Lan [2021] Lan, Q.: Variational quantum soft actor-critic. arXiv preprint:2112.11921 (2021)
  * Chen et al. [2020] Chen, S.Y.-C., Yang, C.-H.H., Qi, J., Chen, P.-Y., Ma, X., Goan, H.-S.: Variational quantum circuits for deep reinforcement learning. IEEE Access 8, 141007–141024 (2020)
  * Skolik et al. [2022] Skolik, A., Jerbi, S., Dunjko, V.: Quantum agents in the gym: a variational quantum algorithm for deep q-learning. Quantum 6, 720 (2022)
  * Brockman et al. [2016] Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., Zaremba, W.: Openai gym. arXiv preprint:1606.01540 (2016)
  * Pérez-Salinas et al. [2020] Pérez-Salinas, A., Cervera-Lierta, A., Gil-Fuster, E., Latorre, J.I.: Data re-uploading for a universal quantum classifier. Quantum 4, 226 (2020)
  * Mnih et al. [2016] Mnih, V., Badia, A.P., Mirza, M., Graves, A., Lillicrap, T., Harley, T., Silver, D., Kavukcuoglu, K.: Asynchronous methods for deep reinforcement learning. In: International Conference on Machine Learning, pp. 1928–1937 (2016). PMLR
  * Mirowski et al. [2016] Mirowski, P., Pascanu, R., Viola, F., Soyer, H., Ballard, A.J., Banino, A., Denil, M., Goroshin, R., Sifre, L., Kavukcuoglu, K., et al.: Learning to navigate in complex environments. arXiv preprint:1611.03673 (2016)
  * Everett et al. [2021] Everett, M., Chen, Y.F., How, J.P.: Collision avoidance in pedestrian-rich environments with deep reinforcement learning. IEEE Access 9, 10357–10377 (2021)
  * Hochreiter and Schmidhuber [1997] Hochreiter, S., Schmidhuber, J.: Long Short-Term Memory. Neural Computation 9(8), 1735–1780 (1997) https://doi.org/10.1162/neco.1997.9.8.1735
  * Schulman et al. [2017] Schulman, J., Wolski, F., Dhariwal, P., Radford, A., Klimov, O.: Proximal policy optimization algorithms. arXiv preprint:1707.06347 (2017)
  * Tang [2019] Tang, Y.: Towards learning multi-agent negotiations via self-play. In: Proceedings of the IEEE/CVF International Conference on Computer Vision Workshops (2019)
  * Bergholm et al. [2018] Bergholm, V., Izaac, J., Schuld, M., Gogolin, C., Ahmed, S., Ajith, V., Alam, M.S., Alonso-Linaje, G., AkashNarayanan, B., Asadi, A., et al.: Pennylane: Automatic differentiation of hybrid quantum-classical computations. arXiv preprint arXiv:1811.04968 (2018)
  * Lockwood and Si [2020] Lockwood, O., Si, M.: Reinforcement learning with quantum variational circuit. In: Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment, vol. 16, pp. 245–251 (2020)
  * Sutton et al. [1999] Sutton, R.S., McAllester, D., Singh, S., Mansour, Y.: Policy gradient methods for reinforcement learning with function approximation. Advances in neural information processing systems 12 (1999)
  * Geva and Sitte [1993] Geva, S., Sitte, J.: A cartpole experiment benchmark for trainable controllers. Control Systems, IEEE 13, 40–51 (1993) https://doi.org/%****␣sn-article.bbl␣Line␣350␣****10.1109/37.236324
  * Kwak et al. [2021] Kwak, Y., Yun, W.J., Jung, S., Kim, J.-K., Kim, J.: Introduction to quantum reinforcement learning: Theory and pennylane-based implementation. In: 2021 International Conference on Information and Communication Technology Convergence (ICTC), pp. 416–420 (2021). IEEE
  * Acuto et al. [2022] Acuto, A., Barillà, P., Bozzolo, L., Conterno, M., Pavese, M., Policicchio, A.: Variational quantum soft actor-critic for robotic arm control. arXiv:2212.11681 (2022)
  * Kandala et al. [2017] Kandala, A., Mezzacapo, A., Temme, K., Takita, M., Brink, M., Chow, J.M., Gambetta, J.M.: Hardware-efficient variational quantum eigensolver for small molecules and quantum magnets. nature 549(7671), 242–246 (2017)
  * Dosovitskiy et al. [2017] Dosovitskiy, A., Ros, G., Codevilla, F., Lopez, A., Koltun, V.: Carla: An open urban driving simulator. In: Conference on Robot Learning, pp. 1–16 (2017). PMLR
  * Bartels and Erbsmehl [2014] Bartels, B., Erbsmehl, C.: Bewegungsverhalten von fußgängern im straßenverkehr, teil 1. FAT-Schriftenreihe (267) (2014)
  * Ba et al. [2016] Ba, J.L., Kiros, J.R., Hinton, G.E.: Layer normalization. arXiv preprint arXiv:1607.06450 (2016)
  * Mitarai et al. [2018] Mitarai, K., Negoro, M., Kitagawa, M., Fujii, K.: Quantum circuit learning. Physical Review A 98(3), 032309 (2018)
  * Schuld et al. [2019] Schuld, M., Bergholm, V., Gogolin, C., Izaac, J., Killoran, N.: Evaluating analytic gradients on quantum hardware. Physical Review A 99(3), 032331 (2019)
  * Rigetti Computing [Accessed: 2023-09-19] Rigetti Computing: Quantum Gate Errors - PyQuil Documentation. Website. https://pyquil-docs.rigetti.com/en/stable/noise.html#quantum-gate-errors
  * King [2003] King, C.: The capacity of the quantum depolarizing channel. IEEE Transactions on Information Theory 49(1), 221–229 (2003)
  * Berezniuk et al. [2020] Berezniuk, O., Figalli, A., Ghigliazza, R., Musaelian, K.: A scale-dependent notion of effective dimension. arXiv preprint arXiv:2001.10872 (2020)
  * Abbas et al. [2021] Abbas, A., Sutter, D., Zoufal, C., Lucchi, A., Figalli, A., Woerner, S.: The power of quantum neural networks. Nature Computational Science 1(6), 403–409 (2021)
  * Grant et al. [2019] Grant, E., Wossnig, L., Ostaszewski, M., Benedetti, M.: An initialization strategy for addressing barren plateaus in parametrized quantum circuits. Quantum 3, 214 (2019)
  * Skolik et al. [2021] Skolik, A., McClean, J.R., Mohseni, M., Smagt, P., Leib, M.: Layerwise learning for quantum neural networks. Quantum Machine Intelligence 3, 1–11 (2021)
  * Holmes et al. [2022] Holmes, Z., Sharma, K., Cerezo, M., Coles, P.J.: Connecting ansatz expressibility to gradient magnitudes and barren plateaus. PRX Quantum 3(1), 010313 (2022)

## Code and Data Availability

All code to generate the data, figures and analyses in this study is publicly
available with detailed information on the implementation via the following
repository: https://github.com/roboak/Nav-Q.


# The category of simple graphs is coreflective in the comma category of
groups under the free group functor

Christian Frank

###### Abstract.

We show that the comma category $(\mathcal{F}\downarrow\mathbf{Grp})$ of
groups under the free group functor $\mathcal{F}:\mathbf{Set}\to\mathbf{Grp}$
contains the category $\mathbf{Gph}$ of simple graphs as a full coreflective
subcategory. More broadly, we generalize the embedding of topological spaces
into Steven Vickers’ category of topological systems to a simple technique for
embedding certain categories into comma categories, then show as a
straightforward application that simple graphs are coreflective in
$(\mathcal{F}\downarrow\mathbf{Grp})$.

##  1\. Introduction

In his 1989 text “Topology Via Logic” [8], Steven Vickers develops a category
$\mathbf{TopSys}$ of topological systems which is noteworthy for containing
both the category of topological spaces as a coreflective subcategory and the
category of locales as a reflective subcategory. In [1], Adamek and Pedicchio
observe that $\mathbf{TopSys}^{\mathrm{op}}$ is equivalent to the comma
category $(\mathbf{Frm}\downarrow\mathbf{CABA})$ of frames over complete
atomic boolean algebras, and further show that $\mathbf{Top}^{\mathrm{op}}$ is
equivalent to the regularly epireflective subcategory of monomorphisms.

Rewritten, $\mathbf{Top}$ is the coreflective subcategory of epimorphisms in

$(\mathbf{Frm}\downarrow\mathbf{CABA})^{\mathrm{op}}=(\mathbf{CABA}^{\mathrm{op}}\downarrow\mathbf{Frm}^{\mathrm{op}}).$

As the category of complete atomic boolean algebras is opposite the category
of sets via taking the powerset, a topological system can be interpreted as a
localic map out of a powerset, ie as an element of the comma category
$(\mathcal{P}\downarrow\mathbf{Loc})$ of locales under the powerset locale
functor $\mathcal{P}:\mathbf{Set}\to\mathbf{Loc}$.

If $2$ is the two-open locale, the hom functor $\hom_{\mathbf{Loc}}(2,-)$
assigns to each locale its set of locale points; this functor is right adjoint
to $\mathcal{P}$. By adjunction, the category of topological systems is also
equivalent to $(\mathbf{Set}\downarrow\hom_{\mathbf{Loc}}(2,-))$.

Note that $\mathbf{Top}$ fits right in the middle of the adjunction
$\mathcal{P}\dashv\hom_{\mathbf{Loc}}(2,-)$. If
$\mathcal{D}_{T}:\mathbf{Set}\to\mathbf{Top}$ is the discrete space functor,
$\mathcal{U}:\mathbf{Top}\to\mathbf{Set}$ the forgetful functor right adjoint
to $\mathcal{D}_{T}$, and $\mathcal{L\dashv S}$ is the locale-spectrum
adjunction between $\mathbf{Top}$ and $\mathbf{Loc}$ (see eg Chapter 2 of
Picado and Pultr [6] for details), then $\mathcal{P}=\mathcal{L\circ D}_{T}$
and $\hom_{\mathbf{Loc}}(2,-)=\mathcal{U\circ S}$.

In this language, $\mathbf{TopSys}\cong(\mathcal{L\circ
D}_{T}\downarrow\mathbf{Loc})\cong(\mathbf{Set}\downarrow\mathcal{U\circ S})$.
Adjuncting into the category $\mathbf{Top}$, we have
$\mathbf{TopSys}\cong(\mathcal{D}_{T}\downarrow\mathcal{S})$. Here
$\mathbf{Top}$ embeds naturally as a composition of unit with counit: the map
$\eta^{\mathcal{L\dashv
S}}\circ\varepsilon^{\mathcal{D}_{T}\dashv\mathcal{U}}:\mathcal{D}_{T}\circ\mathcal{U}\to\mathrm{id}\to\mathcal{S\circ
L}$ gives for each space an object of the comma category
$(\mathcal{D}_{T}\downarrow\mathcal{S})$.

In this paper we investigate conditions for which categories in the center of
two composable adjoint pairs may be embedded nicely into the appropriate comma
categories through this process.

##  2\. The unit-counit composite

Let $\mathbf{B},\mathbf{C},\mathbf{D}$ be complete and cocomplete categories.
Let

$\displaystyle F:\mathbf{B}$ $\displaystyle\rightleftarrows\mathbf{C}:G,$
$\displaystyle L:\mathbf{C}$ $\displaystyle\rightleftarrows\mathbf{D}:R,$

with $F\dashv G$ and $L\dashv R$, and define $\gamma:\mathbf{C}\to(F\downarrow
R)$ by

$\displaystyle\gamma(A)$ $\displaystyle:F(G(A))\to R(L(A)),$
$\displaystyle\gamma(A)$ $\displaystyle:=\eta^{L\dashv
R}_{A}\circ\varepsilon^{F\dashv G}_{A},$ $\displaystyle\gamma(f)$
$\displaystyle:=(G(f)\downarrow L(f)).$

We ask what conditions will ensure that $\gamma$ embeds $\mathbf{C}$ as a
reflective subcategory of the equivalent comma categories

$(\mathbf{B}\downarrow(G\circ R))\cong(F\downarrow R)\cong((L\circ
F)\downarrow\mathbf{D}).$

We can say immediately that $\gamma$ is faithful as soon as either $G$ is or
$L$ is.

Fullness is more precarious. For $A,B$ objects in
$\mathbf{C},f_{\mathbf{B}}\in\hom_{\mathbf{B}}(G(A),G(B))$,
$f_{\mathbf{D}}\in\hom_{\mathbf{D}}(L(A),L(B))$, assume that we have a diagram
in $\mathbf{C}$:

(1) ${(F\circ G)(A)}$${(F\circ G)(B)}$${(R\circ L)(A)}$${(R\circ
L)(B)}$$\scriptstyle{\gamma(A)}$$\scriptstyle{F(f_{\mathbf{B}})}$$\scriptstyle{\gamma(B)}$$\scriptstyle{R(f_{\mathbf{D}})}$

We are interested in conditions that will guarantee that the pair
$(f_{\mathbf{B}},f_{\mathbf{D}})$ is in the image of $\gamma$, that is,
conditions under which the commutativity of (1) implies existence of
$f\in\hom_{\mathbf{C}}(A,B)$ satisfying both $f_{\mathbf{B}}=G(f)$ and
$f_{\mathbf{D}}=L(f)$.

The above diagram expands to:

(2) ${(F\circ G)(A)}$${(F\circ G)(B)}$${A}$${B}$${(R\circ L)(A)}$${(R\circ
L)(B)}$$\scriptstyle{\varepsilon^{F\dashv
G}}$$\scriptstyle{F(f_{\mathbf{B}})}$$\scriptstyle{\varepsilon^{F\dashv
G}}$$\scriptstyle{\eta^{L\dashv R}}$$\scriptstyle{\eta^{L\dashv
R}}$$\scriptstyle{R(f_{\mathbf{D}})}$

Suppose there is some $f^{\prime}\in\hom_{\mathbf{C}}(A,B)$ filling in the
diagram:

(3) ${(F\circ G)(A)}$${(F\circ G)(B)}$${A}$${B}$${(R\circ L)(A)}$${(R\circ
L)(B)}$$\scriptstyle{\varepsilon^{F\dashv
G}}$$\scriptstyle{F(f_{\mathbf{B}})}$$\scriptstyle{\varepsilon^{F\dashv
G}}$$\scriptstyle{\eta^{L\dashv
R}}$$\scriptstyle{f^{\prime}}$$\scriptstyle{\eta^{L\dashv
R}}$$\scriptstyle{R(f_{\mathbf{D}})}$

Then as the diagrams:

${(F\circ G)(A)}$${(F\circ G)(B)}$${A}$${B}$$\scriptstyle{\varepsilon^{F\dashv
G}}$$\scriptstyle{F(G(f^{\prime}))}$$\scriptstyle{\varepsilon^{F\dashv
G}}$$\scriptstyle{f^{\prime}}$${A}$${B}$${(R\circ L)(A)}$${(R\circ
L)(B)}$$\scriptstyle{\eta^{L\dashv
R}}$$\scriptstyle{f^{\prime}}$$\scriptstyle{\eta^{L\dashv
R}}$$\scriptstyle{R(L(f^{\prime}))}$

each also commute, we must have $f_{\mathbf{B}}=G(f^{\prime})$ and
$f_{\mathbf{D}}=L(f^{\prime})$ by the universality of the counit and unit
respectively.

This means that the condition that every diagram of shape (2) can be filled in
as (3) is equivalent to $\gamma$ being full.

One easy way to achieve this is for $\varepsilon^{F\dashv G}$ to be epic at
$A$, for $\eta^{L\dashv R}$ to be monic at $B$, and for one of those two to be
strong. The first two conditions would be guaranteed by faithfulness of $G$
and $L$ respectively. Let’s make that assumption. Since $\mathbf{C}$ is
complete and cocomplete, Proposition 4.3.7(3) of Borceux book 1 [2] tells that
$\varepsilon^{F\dashv G}$ will be strong epic as soon as $G$ is conservative,
and that $\eta^{L\dashv R}$ will be strong monic as soon as $L$ is
conservative.

We conclude:

######  Lemma 1.

If $G$ and $L$ are both faithful and at least one of the two is conservative,
then $\gamma$ is full and faithful.

Note that this is not a necessary condition. In the case of topological
systems, $\mathcal{L}$ is not faithful, as can be seen by looking at maps from
a nonempty space to an indiscrete space with more than one element.

We settle here and turn our attention to the existence of a left adjoint to
$\gamma$.

Following the proof of Theorem 5.2.3 in Rydeheard and Burstall [7],
$(F\downarrow R)$ is complete because $R$ preserves limits and cocomplete
because $F$ preserves colimits. Those limits are constructed from limits in
$\mathbf{B}$ and $\mathbf{D}$, so $\gamma$ preserves limits as soon as both
$G$ and $L$ preserve limits themselves.

$G$ is a right adjoint, so this is only a restriction on $L$. We mention that
in the (dual) case of topological systems, the forgetful functor
$\mathcal{U}:\mathbf{Top}\to\mathbf{Set}$ has both a left adjoint and a right
adjoint.

By Lemma 1 and the special adjoint functor theorem, we conclude the following.

######  Theorem 2.

Let $\mathbf{B},\mathbf{C},\mathbf{D}$ be complete and cocomplete categories,
where $\mathbf{C}$ admits a cogenerating set and is well-powered. Let

$\displaystyle F:\mathbf{B}$ $\displaystyle\rightleftarrows\mathbf{C}:G,$
$\displaystyle L:\mathbf{C}$ $\displaystyle\rightleftarrows\mathbf{D}:S,R,$

with $F\dashv G$ and $S\dashv L\dashv R$. Assume further that both $G$ and $L$
are faithful, and that at least one of the two is conservative. Then
$\mathbf{C}$ is a reflective subcategory of $(\mathbf{B}\downarrow(G\circ
R))\cong(F\downarrow R)\cong((L\circ F)\downarrow\mathbf{D})$ embedded by:

$\displaystyle\gamma$ $\displaystyle:\mathbf{C}\to(F\downarrow R),$
$\displaystyle\gamma(A)$ $\displaystyle:=\eta^{L\dashv
R}_{A}\circ\varepsilon^{F\dashv G}_{A},$ $\displaystyle\gamma(f)$
$\displaystyle:=(G(f)\downarrow L(f)),$

for $A$ and $f$ repectively an object and an arrow of $\mathbf{C}$.

Note that our hypotheses on $\mathbf{C}$ imply that $L$ preserving limits is
equivalent to $L$ admitting a left adjoint $S$.

##  3\. Simple graphs

The theorem requires an adjoint triple $S\dashv L\dashv R$. One such triple is
$\mathcal{D\dashv V\dashv I}$ between $\mathbf{Set}$ and the category
$\mathbf{Gph}$ of simple graphs, where
$\mathcal{V}:\mathbf{Gph}\to\mathbf{Set}$ is the functor taking a simple graph
to its set of vertices, and $\mathcal{D,I}:\mathbf{Set}\to\mathbf{Gph}$ are
the discrete and indiscrete graph functors respectively.

Note that the category $\mathbf{Gph}$ here is the category of reflexive graphs
with no loops, where graph homomorphisms are permitted to collapse adjacent
vertices to a single vertex. This is following the nlab article [4].
$\mathbf{Gph}$ is a Grothendieck quasitopos, which implies that it is locally
presentable, which in turn (along with cocompleteness) implies that it is co-
well-powerered, see [5].

Given a simple graph $G$, the right angled Artin group of $G$ is the quotient
of the free group on the vertices of $G$ by the commutators of adjacent vertex
pairs. This gives a functor $\mathcal{A}:\mathbf{Gph}\to\mathbf{Grp}$.

It is known (referenced in [3]) that $\mathcal{A}$ has a right adjoint
$\mathcal{C}:\mathbf{Grp}\to\mathbf{Gph}$, which takes a group $H$ to its
commutation graph $\mathcal{C}(H)$. The vertices of $\mathcal{C}(H)$ are the
elements of $H$, where two vertices are defined to be adjacent iff they
commute in $H$.

######  Corollary 3.

$\mathbf{Gph}$ embeds as a full coreflective subcategory of
$(\mathcal{F}\downarrow\mathbf{Grp})$, where
$\mathcal{F}:\mathbf{Set}\to\mathbf{Grp}$ is the free group functor.

###### Proof.

The situation looks like:

$\displaystyle\mathcal{D,I}:\mathbf{Set}$
$\displaystyle\rightleftarrows\mathbf{Gph}:\mathcal{V},$
$\displaystyle\mathcal{A}:\mathbf{Gph}$
$\displaystyle\rightleftarrows\mathbf{Grp}:\mathcal{C},$

with $\mathcal{D\dashv V\dashv I}$ and $\mathcal{A\dashv C}$. Here
$\mathcal{V}$ and $\mathcal{A}$ are both faithful, and $\mathcal{A}$ is
conservative. The single-vertex graph is a generator of $\mathbf{Gph}$, and as
noted earlier, the category is co-well-powered.

Because $\mathcal{F=A\circ D}$, the result now follows directly from the dual
to Theorem 2. ∎

The embedding takes a graph to the quotient map from the free group on the
vertices to the right angled Artin group. A homomorphism out of a free group
is isomorphic to a simple graph when it is surjective and its kernel is
generated by commutators of generators.

Our comma category $(\mathcal{F}\downarrow\mathbf{Grp})$ also contains the
category $\mathbf{Grp}$ as a reflective subcategory, embedded by taking a
group to its counit under the free-forgetful adjunction. The left adjoint to
this embedding is simply the codomain projection.

## References

  * [1] J. Adamek and M.-C. Pedicchio.  A remark on topological spaces, grids, and topological systems.  Cahiers Topologie Géom. Différentielle Catég., 38(3):217–226, 1997.
  * [2] Francis Borceux.  Handbook of categorical algebra. 1, volume 50 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, Cambridge, 1994.  Basic category theory.
  * [3] HallaSurvivor (https://math.stackexchange.com/users/655547/hallasurvivor).  How can i compute a monad from this adjunction?  Mathematics Stack Exchange.  URL:https://math.stackexchange.com/q/4029945 (version: 2021-02-18).
  * [4] nLab authors.  category of simple graphs.  http://ncatlab.org/nlab/show/category%20of%20simple%20graphs, March 2021.  Revision 41.
  * [5] nLab authors.  well-powered category.  http://ncatlab.org/nlab/show/well-powered%20category, March 2021\.  Revision 15.
  * [6] Jorge Picado and Aleš Pultr.  Frames and locales.  Frontiers in Mathematics. Birkhäuser/Springer Basel AG, Basel, 2012\.  Topology without points.
  * [7] David E. Rydeheard and Rod M. Burstall.  Computational category theory.  Prentice Hall International Series in Computer Science. Prentice Hall International, Englewood Cliffs, NJ, 1988.  With a foreword by John W. Gray.
  * [8] Steven Vickers.  Topology via logic, volume 5 of Cambridge Tracts in Theoretical Computer Science.  Cambridge University Press, Cambridge, 1989.