# Quantum improvement in Spatial Discretization

Saul Gonzalez  Lighthouse Disruptive Innovation Group Europe, SL. Barcelona -
Spain<EMAIL_ADDRESS>Parfait Atchade-Adelomou  MIT Media
Lab - City Science Group, Cambridge, USA<EMAIL_ADDRESS>Smart Society
Research Group - La Salle - Universitat Ramon Llull, Carrer de Sant Joan de La
Salle, 42, 08022 Barcelona (Spain)  Lighthouse Disruptive Innovation Group,
LLC, 7 Broadway Terrace, Apt 1, Cambridge MA 02139, Middlesex County,
Massachusetts (USA<EMAIL_ADDRESS>
(November 2023)

###### Abstract

Quantum algorithms have begun to surpass classical ones in several computation
fields, yet practical application remains challenging due to hardware and
software limitations. Here, we introduce a quantum algorithm that
quadratically improves spatial discretization within these constraints.
Implemented in the quantum software library Pennylane, our algorithm bridges
the gap from theoretical models to tangible quantum circuitry. The approach
promises enhanced efficiency in quantum spatial analysis, with simulations and
hardware experiments validating its potential.

KeyWords: discretization problem, Grover, quantum arithmetic operators, ISQ
era

##  I Introduction

The ascent of quantum computing marks a pivotal turn in computational
sciences, heralding a new era primed to redefine the paradigms of data
processing and analytical methodologies. Central to this scientific
renaissance is the algorithm we introduce crafted to master the discretization
of continuous spaces, a ubiquitous challenge intersecting numerous scientific
domains Skeel and Berzins (1990); Lustgarten  _et al._ (2008); Grover and
Dimitrakakis (2021).

Transcending classical paradigms, our algorithm operates within the pragmatic
bounds of current quantum hardware infrastructures Atchade-Adelomou (2022). We
trace the algorithm’s journey from theoretical inception to empirical
execution, transmuting its complex underpinnings into quantum simulations.
This seminal contribution is a conduit between the conceptual and the
practical, fostering real-world quantum applications.

Our focus bifurcates into two distinct yet interlinked objectives: the
imperative task of spatial discretization Skeel and Berzins (1990), which
underpins machine learning and spatial trajectory analysis, and the random and
uniform discretization of the feasible region $\Omega_{f}$, articulated as
$\Omega_{f}:=R\setminus(\bigcup_{i=1}^{m}\omega_{i})$, with
$\\{\omega_{i}\\}_{i=1}^{m}$ as a set of areas in this space. In veering from
classical approaches reliant on discriminator function $f$ for point inclusion
within $\Omega_{f}$, we unveil a path less trodden that enhances efficiency
and accuracy.

This treatise not only delineates the quantum computational strides enabled by
our algorithm but also amplifies its far-reaching implications for real-world
scenarios Osher and Paragios (2003). From the geometric precision required in
urban development and vehicular autonomy to the intricate simulations integral
to medical and machine learning breakthroughs, our algorithm is set to
significantly refine the process of transmuting the continuous into the
discrete, outstripping its classical antecedent Sanyal  _et al._ (2010); Funke
_et al._ (2016); Molina  _et al._ (2016); Cao  _et al._ (2014); Fiorini  _et
al._ (2022). With the rise of quantum computing Atchade-Adelomou (2022);
Atchade-Adelomou  _et al._ (2021); Adelomou  _et al._ (2020a); Gonzalez-
Bermejo  _et al._ (2022); Atchade-Adelomou and Larson (2023); Parfait Adelomou
_et al._ (2020); Consul-Pacareu  _et al._ (2023); Atchade-Adelomou and Alonso-
Linaje (2022); Alonso-Linaje and Atchade-Adelomou (2021); Adelomou  _et al._
(2020b, 2023); Atchade-Adelomou  _et al._ (2020), the prospect of more
precise, expedient, and efficient spatial discretization beckons, propelling
an array of vital disciplines into an epoch rich with computational potential
and innovation.

In this work, we delve into the realm of quantum spatial discretization,
aiming to unravel its complexities, enhance its methodologies, and tailor its
implementation for the burgeoning Intermediate-Scale Quantum (ISQ) era
Arrazola and Xanadu (2023). Our expedition is dual-pronged: scrutinizing and
refining spatial discretization’s quantum operations and proffering novel
implementations suited for the ISQ milieu. Through this exploration, we
endeavor to strengthen the nexus between quantum theoretical frameworks and
their palpable applications, equipping both fledgling and seasoned quantum
researchers with cutting-edge tools for spatial discretization.

The manuscript methodically presents research on quantum computing’s role in
spatial discretization. It begins by outlining the motivations and challenges
in quantum computational geometry (Section II). It then reviews existing works
to contextualize the study’s contributions (Section III). Before defining our
methodology, we define the problem to solve in Section (IV), followed by a
foundation of essential quantum concepts applied to geometric problems
(Section V). The method is detailed in Section VI, describing the development
of quantum circuits, operators, and oracles. Section VII validates the
theoretical models with empirical evidence, while the concluding Section IX
reflects on the findings and suggests future research directions, marking the
paper’s progression from quantum theories to their application in
computational geometry.

##  II Motivation and Problem Statement

The advent of quantum computing heralds a transformative era in computational
methodologies, extending the frontier beyond what classical algorithms can
conceive. This research is galvanized by the potential to leverage quantum
mechanics to unravel and navigate the complex terrain of geometric problem-
solving within the extant landscape of quantum technology.

The enigma of spatial discretization looms large in this new paradigm. Whereas
conventional algorithms offer a sturdy foundation, they falter in capturing
geometric spaces’ intricacy and subtlety, a gap that quantum computing is
poised to fill Grover and Dimitrakakis (2021). Our ambition is to refine and
extend classical techniques Braun and Sambridge (1997); Kummer (2017),
offering innovative solutions for discretizing spaces interspersed with
rectilinear, radial, or polygonal obstacles.

We posit that an algorithmic framework rooted in quantum principles will
catalyze a paradigm shift, fostering a sophisticated and adroit analysis of
the feasible region $\Omega_{f}$. To this end, we have implemented and
rigorously tested our algorithm within PennyLane Bergholm  _et al._ (2022).
This discourse is not merely about the theoretical acumen of our algorithm but
its ascendancy into the efficiency of quantum computational geometry,
heralding a new epoch of algorithmic prowess.

##  III Work Context

Spatial discretization, a cornerstone of computational analysis, has
historically been navigated through classical algorithms Braun and Sambridge
(1997); Kummer (2017). These algorithms have provided robust frameworks for
representing geometric spaces in various applications, including urban
planning, computer graphics, and autonomous vehicle navigation. However, they
often encounter challenges in accurately capturing the complexity and nuances
of geometric configurations. This is where quantum computing’s potential
becomes particularly compelling Grover and Dimitrakakis (2021). Our research
aims to harness quantum advancements to refine and extend these classical
techniques, innovating in spatial discretization amidst diverse
obstacles—rectilinear, radial, or polygonal.

In the evolving landscape of quantum computing, significant research has been
dedicated to enhancing spatial search algorithms. A notable contribution from
Ref. Aaronson and Ambainis (2005) delves into the application of Grover’s
quantum search algorithm Grover (1996) in spatial contexts, mainly focusing on
grid structures. The authors challenge previous assertions, demonstrating that
it is feasible to search a $d$-dimensional hypercube in $O(\sqrt{n})$ time for
dimensions $d\geq 3$, and in $O(\sqrt{n}\log^{5/2}n)$ for a two-dimensional
space. This work introduces a novel model of quantum query complexity on
graphs, incorporating considerations from black hole thermodynamics and the
holographic principle, and provides upper and lower bounds for various search
tasks. Additionally, it proposes an $O(\sqrt{n})$-qubit communication protocol
for the disjointness problem, enhancing previous upper bounds and aligning
with quantum communication complexity lower bounds.

Another groundbreaking study on quantum spatial search on a random temporal
network Chakraborty  _et al._ (2017), which investigates the performance of
the continuous-time quantum walk (CTQW) algorithm in locating a marked node on
a random temporal network composed of Erdős-Rényi random graphs $G(n;p)$ RENYI
(1959). This research analytically demonstrates that for any given probability
$p$, there exists an interval of time $\tau$ values for which the algorithm’s
running time is optimal $O(\sqrt{n})$, irrespective of the temporality of the
network. The study reveals a threshold
$p_{\text{temp}}=\frac{\log(n)}{\sqrt{n}}$ where the algorithm is optimal
regardless of $\tau$, showcasing that high temporality can lead to optimal
performance even when $p$ is below the static percolation threshold. The paper
also discusses applying these findings to high-fidelity state transfer between
nodes in a random temporal network, suggesting using temporality as a control
mechanism for quantum information tasks.

Building upon these innovative approaches in quantum spatial search, our work
introduces a quantum algorithm designed to discretize space amidst diverse
obstacles. Our approach leverages quantum computing advancements to surpass
classical algorithms’ limitations in spatial discretization. Through empirical
testing and validation on quantum simulators such as PennyLane, we demonstrate
the superior performance of our algorithm compared to classical methods,
confirming its practicality and efficiency. As the field of quantum
computational geometry continues to grow, our research contributes a
significant advancement, laying the groundwork for future explorations and
broader applications of quantum algorithms in geometric analysis, spatial
discretization, and beyond.

##  IV Problem to solve

We consider a square enclosure $\Omega:=[0,2^{n}]\times[0,2^{n}]$,
representing our workspace. Within this space, a set of areas
$\\{\omega_{i}\\}_{i=1}^{m}$ is defined, which may represent exclusion zones
or areas inaccessible for various reasons, such as physical obstacles or
operational constraints.

The complement of this set called the feasible area
$\Omega_{f}:=\Omega\setminus(\bigcup_{i=1}^{m}\omega_{i})$, constitutes the
region within which we wish to perform a distribution of points. The challenge
lies in generating a set of $N$ points such that their distribution over the
feasible area $\Omega_{f}$ is uniform. This issue arises in various fields,
such as robotics, where the optimal placement of sensors in an environment is
required, or in resource planning in computational geography.

The problem focuses on generating a random sample of points that respects the
constraint of uniformity in distribution over an irregularly shaped space.
This implies not only considering uniformity in point density per unit area
but also addressing the additional complexity imposed by the excluded areas.
Consequently, we seek to develop a method that allows the generation of these
points efficiently and accurately, considering the geometric constraints
imposed by the set $\\{\omega_{i}\\}_{i=1}^{m}$. Fig. (1) illustrates a
specific case of the problem that will be addressed in this article.

Figure 1: Conceptual Illustration of the Generalized Spatial Discretization
Challenge: This figure provides a 2D representation that conceptualizes the
diverse geometric obstacles - rectangular, circular, and convex polygonal -
encountered in spatial discretization problems. It exemplifies the broad scope
of our quantum algorithm, designed to generalize and effectively handle
various obstacle configurations by combining these three fundamental types.

##  V Preliminaries

This section introduces the core concepts and definitions that will be pivotal
in developing our quantum algorithmic solutions. We explore the intricate
relationship between quantum computing and the geometric challenges that arise
in various domains, setting the stage for a deep dive into the innovative
algorithms and techniques proposed in our study.

###  V.1 Notation and Definitions

Building upon our foundational work established Atchade-Adelomou and Gonzalez
(2023), we revisit the bifurcation of operators into two essential
archetypes—Inplace and Outplace—which serve as the cornerstones for the
execution of quantum arithmetic operations. This dichotomy not only
streamlines the algorithmic architecture but also propels the frontiers of
quantum computational techniques, offering a robust scaffold for developing
sophisticated quantum algorithms.

######  Definition 1 (Inplace Operator).

An Inplace Operator applies a function $f:\mathbb{N}\rightarrow\mathbb{N}$
directly onto the input qubit register, such that $U_{f}\ket{x}=\ket{f(x)}$.
This operator overwrites the input $x$ with the output $f(x)$ in the same
register, adhering to the reversibility requirement of quantum computations.
An example is the quantum adder by a constant $k$, denoted as
$Add_{\text{in}}(k)$, which performs the operation
$\ket{x}\rightarrow\ket{x+k}$.

######  Definition 2 (Outplace Operator).

An Outplace Operator for a function $f:\mathbb{N}\rightarrow\mathbb{N}$,
represented by the quantum operator $U_{f}$, operates on two separate qubit
registers. It leaves the original input register $|x\rangle$ unaltered and
outputs the function’s result into an auxiliary register initially set to
$|0\rangle$, resulting in the transformation
$U_{f}|x\rangle|0\rangle=|x\rangle|f(x)\rangle$. This type of operator is
necessary for executing non-bijective functions within quantum computing. An
example is the Outplace quantum adder $Add_{\text{out}}(k)$, which calculates
$Add_{\text{out}}(k)\ket{a}\ket{0}\rightarrow\ket{a}\ket{a+k}$, using an
auxiliary register to hold the result.

We now present the quantum operators pivotal to our methodology for
discretizing spatial spaces in the presence of obstacles. These operators are
delineated as follows:

######  Definition 3 (Interval Check Operator (ICO)).

$ICO$ is a quantum operator used to determine if a given number $x$ is within
a specific interval $(a_{1},a_{2})$. It is formally defined by the action of
the operator on a quantum state:

$ICO(a_{1},a_{2})\ket{0}\ket{x}\ket{0}\ket{0}\mapsto\ket{0}\ket{x}\ket{0}\ket{\text{s}},$
(1)

where $\ket{\text{s}}$ is an ancillary qubit that indicates the result of the
interval check.

######  Definition 4 (Rectangle Inclusion Operator (RIO)).

$RIO$ is a quantum operator that verifies if a point $z$ with coordinates
$(x,y)$ is located within the boundaries of a defined rectangle $R_{i}$. Its
action is represented as:

$RIO(R)\ket{x}\ket{0}\ket{y}\ket{0}\ket{0}\mapsto\ket{x}\ket{0}\ket{y}\ket{0}\ket{s},$
(2)

with $\ket{\text{s}}$ being an ancillary qubit that signifies whether the
point is inside the rectangle.

######  Definition 5 (Multiple Rectangles Inclusion Operator (MRIO)).

$MRIO$ extends the functionality of the Rectangle Inclusion Operator (RIO) to
assess the inclusion of a point in multiple rectangular regions. It is defined
as follows:

$MRIO(\\{R_{i}\\}_{i=1}^{m})\ket{z}\ket{0}\ket{0}\mapsto\ket{z}\ket{0}\ket{\sum_{i=1}^{m}\delta_{i}(z,R_{i})},$
(3)

where $\ket{0}$ denotes an auxiliary qubit register initialized to zero, and
the final qubit accumulates the count of rectangles $R_{i}$ that encompass
point $z:=(x,y)$. The function $\delta_{i}(z,R_{i})=1$ if point $z$ is within
rectangle $R_{i}$, and $\delta_{i}(z,R_{i})=0$ otherwise. This operator
facilitates the simultaneous evaluation of point inclusion across multiple
geometric regions.

######  Definition 6 (Quantum Threshold Comparator ($\hat{T}$)).

$\hat{T}$ is a quantum operator used to determine whether a given quantum
state $\ket{x}$ representing a value $x$ is greater than or equal to a certain
threshold $c$. It encodes this comparison as a binary outcome in an ancillary
qubit $\ket{\alpha}$, which can be used in further quantum computations. The
operator is defined as:

$\hat{T}\ket{x}\ket{0}=\ket{x}\ket{\alpha},$ (4)

where $\ket{\alpha}$ is an ancillary qubit that indicates the result of the
comparison: it is set to $\ket{0}$ if $x\geq c$, and to $\ket{1}$ if $x<c$.

######  Definition 7 (Quantum Negation Operator ($\hat{N}$)).

$\hat{N}$, also known as the quantum bitwise complement operator, negates a
binary number represented in a quantum register. For a number $x$ less than a
predefined modulus $2^{n}$, the operator $\hat{N}$ computes its negation
modulo $2^{n}$, effectively calculating $2^{n}-x$. This is particularly useful
in quantum arithmetic circuits where the inversion of binary values is
required. The action of $\hat{N}$ is given by:

$\hat{N}\ket{0}\ket{x}=\ket{2^{n}-x},$ (5)

where the first quantum register is typically an ancillary qubit initialized
to $\ket{0}$, and $\ket{x}$ is the quantum register holding the value to be
negated.

######  Definition 8 (Outplace Quantum Adder Operator
($\text{Add}_{out}(k)$)).

$\text{Add}_{out}(k)$ is a quantum operator that adds a classical integer $k$
to the quantum state representing an integer $x$ in a quantum register. It
acts on a superposition of states and applies the addition coherently to each
element in the superposition, maintaining quantum parallelism. The operator is
defined as follows:

$\text{Add}_{out}(k)\ket{x}\ket{0}^{\otimes m}=\ket{x+k},$ (6)

where $\ket{x}$ is an $n$-qubit quantum register encoding the integer $x$, and
$\ket{0}^{\otimes m}$ are $m$ ancillary qubits provided to facilitate the
addition, with $m$ typically determined by the space requirements of the
addition operation. The result $\ket{x+k}$ represents the new state of the
quantum register after the addition of $k$.

######  Definition 9 (Inplace Quantum Adder ($Add_{\text{in}}$)).

$Add_{\text{in}}$ is a quantum operator that adds two quantum registers in an
Inplace manner. Given two quantum registers $\ket{a}$ and $\ket{b}$, the
operator $Add_{\text{in}}$ applies the transformation
$\ket{a}\ket{b}\rightarrow\ket{a}\ket{a+b}$. This operator is designed to
preserve the value of the first register $\ket{a}$ while adding it to the
second register $\ket{b}$, updating $\ket{b}$ with the result of the addition.

$Add_{\text{in}}\ket{a}\ket{b}\rightarrow\ket{a}\ket{a+b}.$ (7)

######  Definition 10 (Inplace Quantum Square Adder Operator
($\text{AddSqr}_{in}$)).

$\text{AddSqr}_{in}$ is a specialized quantum operator used for adding the
square of the value encoded in one qubit register to another. Formally, for
qubit registers $\ket{x}$ and $\ket{y}$, the action of $\text{AddSqr}_{in}$ is
defined as:

$\text{AddSqr}_{in}\ket{x}\ket{y}=\ket{x}\ket{y+x^{2}},$ (8)

where, $\ket{x}$ is the input register holding the value to be squared, and
$\ket{y}$ is the target register where the squared value is added.

######  Definition 11 (Outplace Quantum Multiplication Operator
$\text{Mult}_{out}(k)$).

$\text{Mult}_{out}(k)$ is a theoretical construct representing a class of
quantum operations that, given a classical multiplier $k$ and a quantum
register $\ket{x}$ encoding a quantum state, produces a new quantum state
where the quantum register is entangled with an ancillary register to
represent the product $kx$. The operator is defined as:

$\text{Mult}_{out}(k)\ket{x}\ket{0}:=\ket{x}\ket{kx},$ (9)

where $\ket{x}$ is the original quantum state, $\ket{0}$ is the initial state
of the ancillary quantum register, and $\ket{kx}$ represents the quantum state
after the application of the multiplication operation.

######  Definition 12 (Outplace Quantum Absolute Difference Circuit
($\text{AbsDiff}_{out}$)).

Let $\ket{x}$ be a quantum state encoding the binary representation of a
number $x$, and let $k$ be a classical number. The _Quantum Absolute
Difference Circuit_ is a quantum operation that transforms an initial state
$\ket{x}\ket{0}\ket{0}\ket{0}$ into a final state
$\ket{x}\ket{0}\ket{0}\ket{|x-k|}$, where $\ket{|x-k|}$ encodes the absolute
difference between $x$ and $k$. This operation is represented as:

$\text{AbsDiff}_{out}(k)\ket{x}\ket{0}\ket{0}\ket{0}\rightarrow\ket{x}\ket{0}\ket{0}\ket{|x-k|}.$
(10)

These operators will be used to construct the quantum circuits necessary for
efficiently discretizing spaces with obstacles. They will be employed within
Grover’s algorithm to enhance the process of finding a feasible region within
a discretized space.

###  V.2 Quantum Discretization Across Geometric Landscapes

Quantum algorithmic geometry often encounters various obstacles, especially in
discretizing spatial environments. Our approach classifies these into three
primary scenarios—rectangular, circular, and convex polygonal obstacles—each
demanding specific quantum computational strategies:

  * •

Rectangular Obstacles: These are common in engineered environments, presenting
orthogonal spatial challenges requiring specialized quantum solutions.

  * •

Circular Obstacles: Frequently encountered in applications where radial
symmetry is a factor, they require custom quantum discretization techniques.

  * •

Convex Polygonal Obstacles: These cover a wide range of geometric shapes,
crucial in graphical simulations and design, where quantum computations must
be precise.

Our framework constructs quantum oracles for each obstacle type, which are
vital components of our algorithmic solution. This process involves creating
specific quantum circuits and leveraging Grover’s algorithm Grover (1996) to
enhance the efficiency and precision of the discretization process.

In dealing with Rectangular Obstacles, our approach includes circuits designed
for point inclusion verification, utilizing operators for boundary checks and
summation. In the Circular Obstacle scenario, we employ circuits that
integrate general addition, absolute value computation, and distance
measurement operations. When addressing Convex Polygonal Obstacles, the focus
shifts to integer arithmetic within quantum environments, which involves using
operators for scalar arithmetic and vector cross-products.

These detailed circuit designs, tailored for specific obstacle types, are
adaptable for environments with multiple shapes. The upcoming sections will
delve deeper into these concepts, exploring the algorithmic nuances and the
strategic development of quantum gates and circuits. This is essential for
achieving our discretization goals within these varied geometric landscapes.

Our methodology addresses the general case by considering these three obstacle
types: rectangular, circular, and convex polygons. This comprehensive approach
lays the foundation for effectively managing and representing obstacles in
diverse spatial discretization applications.

##  VI Implementation

###  VI.1 Spatial Discretization Through a Quantum Algorithm

Suppose we have access to a function, which we will call
$O:\mathbb{R}^{2}\rightarrow\\{0,1\\}$, that determines if a point $z:=(x,y)$
is within the feasible area. Let $A_{f}$ be the area of the feasible region
and $A_{t}$ the total area; then the probability of randomly choosing a point
in the viable area is $p:=\frac{A_{f}}{A_{t}}$. If this probability is
unknown, it can be estimated simply using an algorithm like Monte Carlo
Metropolis (1909); Grover (1996); Hansmann and Okamoto (1999). Suppose we want
to discretize the plane into $N$ points. Using classical computing techniques,
the general strategy consists randomly selects a point from space and checks
whether the function is in the feasible area with the function $O$. The
expected number of times we would need to use the function $O$ following this
method is $\frac{N}{p}$. However, this technique can be improved with quantum
computing. By applying Grover’s algorithm Grover (1996), we can reduce this
number. If $p$ is the probability of choosing a point in the feasible area,
Grover’s algorithm theory tells us that by applying Grover’s iterator
$O(\frac{1}{\sqrt{p}})$ times, we can find a point in the feasible area with a
probability close to 1. This approach reduces the number of times we need to
apply the oracle to $O(\frac{N}{\sqrt{p}})$ (please refer to the mathematical
demonstration in Appendix (A)), thus achieving a quadratic improvement over
the classical case. Fig. (2) schematizes the theory we have just developed.

Figure 2: Quantum circuit utilizing Grover’s algorithm to efficiently
discretize the feasible region $\Omega_{f}$. The circuit is repeated $N$ times
to achieve the desired discretization.

By repeating this circuit $N$ times, we acquire $N$ points that make up the
desired discretization of the region. One of the primary challenges when
applying Grover’s algorithm is constructing the quantum oracle. In the
following sections, we offer detailed examples for various scenarios and
explain how to implement the oracle for each case.

###  VI.2 Oracle for Rectangular Obstacle Problems

This section details the construction of Grover’s oracle tailored for
environments featuring rectangular obstacles. Fig. (3) presents the
rectangular obstacle with all the variables for constructing the oracle.

Figure 3: This figure illustrates the rectangular obstacle and given a point
$z=(x,y)$ falls within a rectangular boundaries. Each rectangle is defined by
its corner coordinates: $(a_{1},b_{1})$, $(a_{1},b_{2})$, $(a_{2},b_{1})$, and
$(a_{2},b_{2})$.

We consider a point $z$ situated within a two-dimensional plane, described by
the coordinate pair $(x,y)$. The coordinates $x$ and $y$ specify the point’s
location along the horizontal and vertical axes. Our objective is to ascertain
whether the point $z$, represented quantumly as
$\ket{x_{1},\ldots,x_{n}}\ket{y_{1},\ldots,y_{n}}$, lies within a specified
rectangular region. This region is defined by the Cartesian product of
intervals $(a_{1},a_{2})$ and $(b_{1},b_{2})$. To achieve this, we deploy a
set of three distinct quantum operators:

  * •

$ICO$: Checks if $a_{1}\leq x\leq a_{2}$. See Equation (1).

  * •

$RIO$: Verifies if $(x,y)$ is inside the rectangle $R$. See Equation (2).

  * •

$MRIO$: Determines if a point $(z)$ lies within any given rectangle. See
Equation (3).

We present the circuit $ICO$ which verifies if a number $x\in\mathbb{N}$ is
within the interval $(a_{1},a_{2})$ (see Figure 4).

Figure 4: Quantum circuit for the $ICO$ operator, checking if a number $x$ is
within the interval $(a_{1},a_{2})$. The solution remains in the $s$ register.

The $ICO$ operator uses an auxiliary qubit to store the result and requires
three additional qubits. The construction of the $RIO$ operator is depicted in
Figure 5.

Figure 5: The Quantum circuit for the $RIO$ operator confirms whether a point
$(x,y)$ lies within the i-th rectangle, denoted as $R_{i}$. Figure 6: Quantum
circuit for the $MRIO$ operator, verifying if a point $z$ is inside a
rectangle $\\{R_{i}\\}_{i=1}^{m}$.

The MRIO operator 6 requires using three auxiliary qubits to implement $ICO$,
two more auxiliary qubits for storing its outcomes, and an additional qubit
for the final result, amounting to six qubits. Once $RIO$ is constructed,
developing $MRIO$ for multiple rectangles becomes straightforward. It simply
involves applying $RIO$ for each of the available rectangles. As defined in
the construction of the $RIO$ operator, each of these operators takes the set
$R_{i}:=(a_{i1},a_{i2},b_{i1},b_{i2})$ as parameters, which define the
rectangle $(a_{i1},a_{i2})\times(b_{i1},b_{i2})$. Let us recall Eq. (2), and
from it, let us explain its evolution through Fig. (5) as follows:

  * •

$\psi_{1}:=\ket{x}\ket{s_{1}}\ket{y}\ket{s_{2}}\ket{s}$: After applying the
$RIO$ operator to the $x$ and $y$ registers, the auxiliary qubits are employed
to determine if these values fall within the specified intervals.

  * •

$\psi_{2}:=\ket{x}\ket{0}\ket{y}\ket{0}\ket{s}$: Upon completion of the
algorithm, the last qubit stores the outcome, indicating whether the point
resides within the desired interval.

Let us recall the definition of $MRIO$ (3) and explain the algorithm’s
intermediate steps. We already know that $\delta_{i}=1$ when the point $z$
belongs to the rectangle $R_{i}$, and $\delta_{i}=0$ otherwise, then the steps
are as follows:

  * •

$\psi_{1}:=\ket{z}\ket{0}\ket{\delta_{1}}$. Initially, we check if the point
$z$ belongs to the rectangle $R_{1}$. If it does, we add one to the last
register.

  * •

$\psi_{2}:=\ket{z}\ket{0}\ket{\delta_{1}+\delta_{2}}$. We repeat the procedure
for the second rectangle.

  * •

$\psi_{3}:=\ket{z}\ket{0}\ket{\sum_{i=1}^{n}\delta_{i}}$. After checking if
the point $z$ belongs to each of the rectangles, the last register will hold
the value of the number of rectangles to which the point $z$ belongs.

###  VI.3 Oracle for Circular Obstacle Problems

Our quantum oracle is crafted to discern whether a point $(x,y)$ falls outside
the boundary of a circular obstacle, defined by centers
$\\{c_{i}\\}_{i=1}^{m}$ and radii $\\{r_{i}\\}_{i=1}^{m}$. Fig. (7) presents
the circular obstacle with its variables.

Figure 7: This figure illustrates the circular obstacle with a given point
$z=(x,y)$. A center has two coordinates ($c_{1},c_{2}$) and a radius ($r$)
that define each circular obstacle, and the circuit evaluates whether the
point $z=(x,y)$ lies outside these circular regions.

The exclusion condition for a point from a circular obstacle’s area is given
by:

$r_{i}^{2}\leq(x-c_{1i})^{2}+(y-c_{2i})^{2}.$ (11)

To address the non-bijectivity challenge of the quadratic function
$h(x):=(x-c_{1})^{2}$ in quantum computation, we employ the Quantum Threshold
Comparator ($\hat{T}$) (4) and the Quantum Negation Operator ($\hat{N}$) (5)
which are central to computing the Euclidean distance following Equation 11.

But, before computing the Euclidean distance, we must construct all the
ingredients to reach this point. First, we must construct the AbsDiff operator
defined in Eq. (10).

The binary variable $\alpha$ (12), which indicates whether $x$ is greater or
less than $c_{1}$, is determined as follows:

$\alpha:=\begin{cases}0&\text{if }c_{1}\leq x,\\\ 1&\text{if
}x<c_{1}.\end{cases}$ (12)

Using $\alpha$, the function $f(x)$ (13) for computing the absolute difference
needed for the Euclidean distance is defined by:

$f(x)=(1-\alpha)(x-c_{1})+\alpha(-x+c_{1}).$ (13)

When $x<c_{1}$, the Quantum Negation Operator $\hat{N}$ (5) is used to
calculate $-x$.

The quantum circuit implementing Equation 13 is illustrated in Figure 8, which
depicts the temporal evolution of the quantum state and necessitates the
following operators:

Figure 8: Quantum State Evolution for the Circular Obstacle Oracle. This
sequence depicts the intricate process of computing absolute distances and
resetting the system: $\psi_{1}$ initiates with the encoding of primary
values; $\psi_{2}$ and $\psi_{3}$ engage in conditional operations to compute
the absolute difference $|x-c_{1}|$, where $c_{1}$ represents the center of
the circular obstacle; $\psi_{4}$ through $\psi_{6}$ culminate the computation
process and systematically reset the ancillary qubits for future computations,
ensuring the efficient and reusable nature of the quantum oracle.

The evolution of the circuit’s state is detailed step-by-step, elucidating the
critical role of $\hat{T}$ and $\hat{N}$ in facilitating the quantum
computation of the Euclidean distance, thus validating our approach for
solving circular obstacle problems within a quantum context.

This oracle exemplifies the application of quantum computational techniques to
classical geometric problems and showcases the potential for significant
advancements in quantum navigation algorithms.

Reordering (13), we get to Eq. (14)

$f(x)=(1-2\alpha)(x-c_{1}).$ (14)

Once we have this operator, we can proceed as follows.

Let us examine how the circuit’s state from Fig. (8) evolves at each labeled
step.

  * •

$\psi_{1}:=\ket{x}\ket{\alpha}\ket{0}\ket{x}$: Initially, the state $\psi_{1}$
represents the system after the application of operator $\hat{T}$, which
encodes the value of $\alpha$ based on the comparison of $x$ and $c_{1}$. The
ancillary qubits are in their initialized states, and the register holds the
value of $x$.

  * •

$\psi_{2}:=\ket{x}\ket{\alpha}\ket{(1-\alpha)x+\alpha(2^{n}-x)}$: At this
juncture, the circuit has engaged in a conditional operation based on the
value of $\alpha$. The state remains unchanged if $\alpha$ is 0, indicating
$x\geq c_{1}$. Otherwise, the system negates $x$, calculating $2^{n}-x$.

  * •

$\psi_{3}:=\ket{x}\ket{\alpha}\ket{(1-\alpha)x+\alpha(2^{n}-x+c_{1})}$: The
state $\psi_{3}$ reflects the addition of $c_{1}$ to the negated value of $x$
when $\alpha$ is 1. This is part of the process to compute the absolute
difference $|x-c_{1}|$.

  * •

$\psi_{4}:=\ket{x}\ket{\alpha}\ket{(1-\alpha)x+\alpha(c_{1}-x)}$: Here, the
system corrects the earlier negation by subtracting $2^{n}$ when $\alpha$ is
1, completing the computation of $|x-c_{1}|$.

  * •

$\psi_{5}:=\ket{x}\ket{\alpha}\ket{0}\ket{(1-\alpha)(x-c_{1})+\alpha(c_{1}-x)}$:
At this stage, $\psi_{5}$ shows the ancillary qubits being reset, leaving the
final qubit register with the absolute difference computed, ready for further
operations.

  * •

$\psi_{6}:=\ket{x}\ket{0}\ket{0}\ket{(1-2\alpha)(x-c_{1})}$: Finally, we
reapply the operator $\hat{T}^{\dagger}$ to not compute the value of $\alpha$,
resetting the auxiliary qubit, and leaving the system with only the calculated
absolute difference. This step is crucial for restoring the system to a state
where the additional qubits can be reused for subsequent computations without
carrying over any information from the previous operation.

Once we know how to calculate $h(x)=|x-c_{1}|$, the rest of the operations are
straightforward.

The quantum state’s evolution in the circular obstacle oracle unfolds through
precise arithmetic operations. We detail the progression from $\psi_{1}$ to
$\psi_{3}$, revealing the complex computational evolution depicted in Fig.
(9):

  * •

$\psi_{1}:=\ket{x,|x-c_{1}|,y,|y-c_{2}|,0}$ represents the quantum register
initialized with the coordinate values and ancillary qubits prepared to encode
the Euclidean distance computation’s intermediate steps. This state captures
the preparation phase where the groundwork for distance calculations is laid.

  * •

The system progresses to the execution of the squared distance computation
transitioning to $\psi_{2}:=\ket{x}\ket{\mid x-c_{1}\mid}\ket{y}\ket{\mid
y-c_{2}\mid}\ket{\mid x-c_{1}\mid^{2}}$, At this juncture, the ancillary
qubits store the squared terms of the Euclidean distance, a pivotal step that
converges towards determining point-to-obstacle proximity.

  * •

Lastly, unveils the quantum register post ’uncomputation’
$\psi_{3}:=\ket{x}\ket{|x-c_{1}|}\ket{y}\ket{|y-c_{2}|}\ket{|x-c_{1}|^{2}+|y-c_{2}|^{2}}$.
This state demonstrates the quantum circuit’s reversibility, where ancillary
qubits are reset, and the register is restored to a near-initial state—without
the last qubit, which now holds the essential computed value for the
discretization task.

The quantum state evolution within the oracle reflects a work of quantum
arithmetic, ensuring the reversibility of computations—fundamental to quantum
mechanics. This procedural integrity is vital for precisely determining
spatial relationships between a point and circular obstacles, epitomizing the
remarkable efficiency of quantum computation.

The requisite qubit allocation for the oracle is as follows:

  * •

A total of $2n$ qubits are allocated for encoding the coordinate variables $x$
and $y$.

  * •

An ensemble of $2n+1$ qubits is dedicated to calculating the squared Euclidean
distance, specifically $|x-c_{1}|^{2}+|y-c_{2}|^{2}$.

  * •

An additional $n+1$ auxiliary qubits are employed to assist in the
intermediate computations, namely $|x-c_{1}|$ and $|y-c_{2}|$.

Consequently, implementing this quantum circuit requires $5n+1$ qubits,
optimizing the oracle construction to a more efficient requirement of $3n+1$
qubits, exemplifying optimal resource utilization within quantum computational
frameworks.

Figure 9: Stages of quantum state evolution in Euclidean distance calculation.
Starting with $\psi_{1}:=\ket{x,|x-c_{1}|,y,|y-c_{2}|,0}$, the register is
initialized and prepared for encoding the Euclidean distance. The state
$\psi_{2}:=\ket{x}\ket{|x-c_{1}|}\ket{y}\ket{|y-c_{2}|}\ket{|x-c_{1}|^{2}}$
advances the calculation by squaring the encoded distances, storing essential
terms for proximity evaluation. The final state
$\psi_{3}:=\ket{x}\ket{|x-c_{1}|}\ket{y}\ket{|y-c_{2}|}\ket{|x-c_{1}|^{2}+|y-c_{2}|^{2}}$
reflects the register after uncomputation, resetting ancillary qubits and
leaving the computed squared distance in the last qubit.

###  VI.4 Oracle for Convex Polygon Problems

In cases where obstacles are generalized convex polygons, we aim to verify
that each point lies within the polygon. Should the polygon be concave, a
subdivision technique into convex polygons is applicable. Fig. (10) presents a
convex polygon obstacle and its variables.

Figure 10: This figure illustrates a convex polygonal obstacle to ascertain
whether a point $z=(x,y)$ is located within the confines of an eight-sided
polygon. The polygon is defined by a sequence of eight vertices
$\\{v_{1},v_{2},\ldots,v_{8}\\}$ and corresponding edge vectors
$\\{p_{1},p_{2},\ldots,p_{8}\\}$. The circuit evaluates the spatial
relationship between point $z$ and each polygon edge to determine whether $z$
falls inside the polygonal boundary.

We consider the following scenario: a convex polygon whose $m$ sides are
defined by a set of vertices $\\{p_{i}\\}_{i=1}^{m}$ and vectors
$\\{v_{i}\\}_{i=1}^{m}$. To ascertain whether a point $(x,y)$ falls to the
left or right side of the line $\\{p_{i}+\lambda
v_{i}:\lambda\in\mathbb{R}\\}$, where the sign of the cross products
$(p_{i}-z)\land v_{i}$ needs to be calculated.

For the calculations just described, it is necessary to employ integer
arithmetic Şahin (2020).

####  VI.4.1 Construction of the Oracle

Consider a polygon delineated by a sequence of vertices
$\\{p_{i}\\}_{i=1}^{M}$. We construct vectors
$v_{i}:=\overline{p_{i}p_{i+1}}$, where each $v_{i}$ connects consecutive
vertices $p_{i}$ and $p_{i+1}$. Collectively, these vertices and vectors give
rise to the series of defining lines $\\{R_{i}\\}_{i=1}^{M}$. Inclusion of a
point $x$ within the polygon is affirmed if all the vector cross-products
$(x-p_{i})\times v_{i}$ consistently share the same sign, indicating that $x$
consistently lie on the same side of each line $R_{i}$ (see Fig. (10)). To
facilitate this verification, we introduce a quantum circuit responsible for
calculating the vector cross-products, integrating both quantum and classical
vectors, as depicted in Fig. (11).

####  VI.4.2 Cross-Product Computation in Quantum Circuits

The crux of evaluating a point’s position relative to a polygonal boundary
lies in computing the vector cross-product. This necessitates a quantum
circuit (see Fig. 11) that operationalizes the following transformation:

$\begin{split}VCP(v_{1},v_{2})\ket{S_{x}}\ket{x}\ket{S_{y}}\ket{y}\ket{0}\mapsto\\\
\ket{S_{x}}\ket{x}\ket{S_{y}}\ket{y}\ket{xv_{2}-yv_{1}},\end{split}$ (15)

where $VCP(v_{1},v_{2})$ is a unitary operator that maps the inputs to the
cross-product of two-dimensional vectors, a fundamental operation in
determining the positional relation of a point to the edges of a polygon.

To facilitate this calculation, our approach integrates integer arithmetic
within the quantum framework, utilizing two complementing notations: absolute
value-sign notation for efficient multiplication and two’s complement notation
for straightforward addition, as introduced by Baugh and Wooley Baugh and
Wooley (1973). These notations enable the quantum circuit to perform
arithmetic operations with enhanced simplicity and precision. At the heart of
this arithmetic process is the multiplication operator $Mult$, defined for
natural numbers $x$ in Equation (9). Through the application of $Mult$, our
circuit (11) achieves the cross-product, enabling the quantum evaluation of
point inclusion in polygonal regions with unprecedented efficiency. Then, the
resultant quantum circuit is as follows:

Figure 11: Quantum circuit for the Cross-Product Operator as defined in
Equation 15. The initial state $\psi_{1}$ reflects the computation of the term
$v_{1}x$, setting up for the cross-product. The subsequent state $\psi_{2}$
captures the completion of the cross-product with the result $xv_{2}-yv_{1}$,
illustrating the critical step in vector operations within quantum computing.

  * •

The quantum state is given by
$\psi_{1}=\ket{s_{x}}\ket{x}\ket{s_{y}}\ket{y}\ket{v_{1}x}$. After applying
the first part of the circuit, we obtain the desired calculation.

  * •

The circuit output is observed on
$\psi_{2}=\ket{s_{x}}\ket{x}\ket{s_{y}}\ket{y}\ket{v_{2}x-v_{1}y}$.

Recalling that, we aim to verify if a point $z:=(x,y)$ is inside the polygon,
let $M$ be the number of sides of the polygon and let $f$ be the function
defined by $f(v_{i},p_{i})\ket{z}\ket{0}\rightarrow\ket{z}\ket{(z-p)\times
v_{i}}$. A point lies within the polygon if the sign of all the cross-products
$(z-p_{i})\times v_{i}$ is positive for every $i$. We define the function
$g(z,v_{i},p_{i})$, which equals $0$ if the point $z$ is on the correct side
of the line $\\{p_{i}+\lambda v_{i}:\lambda\in\mathbb{R}\\}$ and $1$ if it is
on the incorrect side. Hence, we can construct the circuit (12) accordingly.

Figure 12: Quantum circuit for verifying a point’s inclusion within a polygon
using the cross-product function $f$ by iteratively computing and resetting
vector cross-products for each polygon edge, with controlled operations
indicating the point’s position relative to the polygon’s boundaries.

Each step in the circuit and its impact on the quantum state is detailed,
illustrating the process for determining the point’s inclusion within the
polygonal area as depicted in Figure 12.

We now consider the operations necessary to determine whether a point is
within a polygon. Let us represent a polygon as a sequence of vertices
$\\{v_{i}\\}_{i=1}^{n}$ such that the sides of the polygon are formed by the
segments $e_{i}:=v_{i}\to v_{i+1}$ for $i\in\\{1,...,n\\}$ (here,
$v_{1}=v_{n+1}$). The vertices should be ordered so that the edges $e_{i}$ are
correctly oriented, meaning that the polygon’s interior remains to the left of
the edge being traversed. Once the polygons are defined in this manner, to
check whether a point $p$ belongs to the interior of the polygon, it must
satisfy $(p-v_{i})\land e_{i}>0$ for all $i$. In other words, the point $p$
must lie to the left of each edge forming the sides. We then consider the
operator $f$ defined as follows:

$f(v_{i},e_{i})\ket{z}=\ket{(z-v_{i})\land e_{i}}$ (16)

To devise the function $f$, it is essential to utilize the $Add_{in}$
operator, adapted to perform subtraction operations (refer to Eq. (7)).
Additionally, the $VCP$ (Vector Cross Product) operator is employed for
executing vector cross-product calculations (as delineated in Eq. (15)).
Consequently, a point is determined to be inside the polygon if the condition
$\sum_{i=1}^{n}f(v_{i},e_{i})\ket{z}=0$ is satisfied. Figure (12) presents the
quantum circuit designed to ascertain whether a point $z$ resides within the
confines of a polygon delineated by the vertices $\\{v_{i}\\}_{i=1}^{n}$.

Let us examine the state of the circuit at each intermediate step for
inclusion within the paper.

  * •

$\psi_{1}$ is defined as $\ket{z}\ket{(z-p_{1})\times
v_{1}}\ket{g(z,v_{1},p_{1})}$. Here, we evaluate the point $z$ against the
line defined by $\\{p_{1}+\lambda v_{1}:\lambda\in\mathbb{R}\\}$.

  * •

For $\psi_{2}$, we have $\ket{z}\ket{(z-p_{2})\times
v_{2}}\ket{g(z,v_{1},p_{1})+g(z,v_{2},p_{2})}$. The comparison is now with the
line $\\{p_{2}+\lambda v_{2}:\lambda\in\mathbb{R}\\}$.

  * •

In $\psi_{3}$, the state is $\ket{z}\ket{(z-p_{n})\times
v_{n}}\ket{\sum_{i=1}^{n}g(z,v_{i},p_{i})}$. The point $z$ is juxtaposed with
the line $\\{p_{n}+\lambda v_{n}:\lambda\in\mathbb{R}\\}$.

  * •

Finally, $\psi_{4}$ is represented as
$\ket{z}\ket{0}\ket{\sum_{i=1}^{n}g(z,v_{i},p_{i})}$. The ancillary register
values are reset to their initial state in the last step.

This sequence of states $\psi_{1}$ to $\psi_{4}$ articulates the computational
procedure for determining the relative position of a point $z$ concerning a
sequence of lines, each represented by a point $p_{i}$ and a direction vector
$v_{i}$. The function $g$ computes the cross-product and contributes to a
cumulative sum that ultimately discerns the point’s inclusion within the
polygon defined by these lines. The final step ensures the reversibility of
the quantum operations by resetting the ancillary qubits.

##  VII Results

This section presents the empirical validation of our quantum algorithms
designed to tackle spatial discretization in the presence of various geometric
obstacles. Through a series of simulations and quantum circuit
implementations, we demonstrate the effectiveness of our proposed methods
across three distinct scenarios: rectangular in Fig. (13), circular in Fig.
(14), and convex polygonal obstacles in Fig. (16). As a part of a result of
our work, fig. (17) shows the quadratic improvement of the quantum algorithm
over the classical approach. The performance of each operator, integral to the
function of the quantum oracles, is scrutinized to ascertain their
contribution to the overall efficacy of the algorithm. As a result, tables (1)
and (2) summarize the operators created as contributions and ingredients to
respond to the problem of spatial discretization.

###  VII.1 Rectangular Obstacle Scenario

In the rectangular obstacle scenario, we utilized the Interval Check Operator
(ICO), Rectangle Inclusion Operator (RIO), and Multiple Rectangles Inclusion
Operator (MRIO) within our quantum circuits. The ICO accurately determined the
inclusion of points within specified intervals, while the RIO successfully
verified point inclusion within individual rectangles. The MRIO extended this
functionality to multiple rectangles, showcasing the scalability of our
approach. The results figures can be analyzed in Fig. (13).

Figure 13: This figure displays the various tests we have conducted. We
selected ten red points that do not belong to the rectangles. We then applied
Grover’s algorithm and demonstrated that the points returned were within the
feasible zone.

###  VII.2 Circular Obstacle Scenario

For circular obstacles, the Quantum Threshold Comparator ($\hat{T}$) and the
Quantum Negation Operator ($\hat{N}$) were pivotal. The $\hat{T}$ efficiently
encoded the binary variable $\alpha$, indicating the relation between a point
and the circle’s center, while $\hat{N}$ calculated the negation modulo
$2^{n}$, crucial for the distance computations. The operators collectively
facilitated the construction of an oracle that accurately discerned point
exclusion from circular areas. The circular obstacle scenario’s results
figures can be analyzed in Fig. (14).

Figure 14: This figure displays the various tests we have conducted. We
selected nine red points that do not belong to the circular obstacle. We then
applied Grover’s algorithm and demonstrated that the points returned were
within the feasible zone.

###  VII.3 Convex Polygonal Obstacle Scenario

In dealing with convex polygonal obstacles, the quantum circuit effectively
computed vector cross-products using the Quantum Adder Operator (Add(k)) and
the Quantum Multiplication Operator(Mult(k)). These operators allowed the
circuit to evaluate whether a point resided within the polygon by checking the
sign consistency of cross-products, which is a quantum computational
reflection of the left-hand rule. Fig. (15) and (16) show the convex polygonal
obstacle scenario’s results figures.

Figure 15: This figure displays the various tests we have conducted. We
selected 1 red point that does belong to the polygon and tested that the green
point was within the feasible zone.

Figure 16: This figure displays the various tests we have conducted. We
selected 3 red points that do not belong to the polygonal obstacle. We then
applied Grover’s algorithm and demonstrated that the points returned were
within the feasible zone.

The diverse range of operators implemented and tested herein lays the
foundation for more complex geometric processing tasks within the quantum
domain. Our findings not only validate the utility of these operators but also
serve as a testament to the potential of quantum algorithms to empower
computational geometry.

Table 1: Quantum operators implemented in the algorithm with their respective resource requirements. The number of qubits required, the count of auxiliary qubits, and the depth of each operator’s circuit are crucial factors for assessing the algorithm’s complexity and feasibility on quantum hardware. The number of rectangular obstacles is the variable $m$ in the $MRIO$ operator. Operator | Input Qubits | Output Qubits | Auxiliary Qubits | Depth
---|---|---|---|---
$ICO(a_{1},a_{2})$ | $n$ | 1 | 3 | $O(n^{2})$
$RIO(R)$ | $n$ | 1 | 5 | $O(n^{2})$
$MRIO(\\{R_{i}\\}_{i=1}^{m})$ | $n$ | $\log_{2}(m)$ | 6 | $O(n^{2})$
$\hat{T}$ | $n$ | 1 | 1 | $O(n^{2})$
$\hat{N}$ | $n+1$ | 0 | 0 | $O(n^{2})$
$Mult$(k) | $n$ | $2n$ | 0 | $O(n^{2})$
$\textit{Add\\_{in}}(k)$ | $n$ | 0 | 0 | $O(n^{2})$
$Add\\_{in}$ | $n$ | 0 | 0 | $O(n^{2})$
$AbsDiff(k)$ | $n+1$ | $n+1$ | 2 | $O(n^{2})$
$AddSqr_{in}$ | $n$ | $2n$ | 0 | $O(n^{2})$
$ED_{in}(c_{1},c_{2})$ | $2n$ | $2n$ | $n+1$ | $O(n^{2})$
$VCP(v_{1},v_{2})$ | $2n$ | $2n$ | 1 | $O(n^{2})$

##  VIII Discussion

This section elucidates the significant advancements made in the field of
quantum algorithmic geometry through the development of our quantum algorithm.
A critical aspect of our research is demonstrating the quadratic improvement
of our algorithm’s performance over classical methods. We have substantiated
this improvement through a rigorous analytical framework and simulations,
depicted in a comparative graph (see Figure (17)). We also provide a
demonstration ((A)), showcasing the quadratic improvement that is reflected in
the comparative Fig. (17)

Figure 17: Comparative performance graph showing the quadratic improvement of
the quantum algorithm over the classical approach in the task of Spatial
discretization. The x-axis represents the input size, while the y-axis
indicates the number of Oracle applications required. The quantum algorithm’s
curve illustrates a markedly lower growth rate, confirming its superior
efficiency.

Implementing our quantum algorithm involved developing a series of quantum
operators, each integral to the spatial discretization process. These
operators were ingeniously crafted to align with the capabilities and
limitations of current quantum computing technology, ensuring both theoretical
robustness and practical applicability. Table 1 provides a comprehensive
summary of these operators, detailing the number of qubits required, their
specific roles within our algorithm, and their computational depth. Notably,
the computational depth, predominantly $O(n^{2})$ due to applying the Quantum
Fourier Transform (QFT), could be optimized for the actual quantum era. Our
scope is the Intermediate-Scale Quantum (ISQ) systems Arrazola and Xanadu
(2023). Our approach thus stands as a testament to the adaptability and
scalability of quantum algorithms in tackling complex geometric problems.

Operator | Symbol |  Description
---|---|---
Interval Check Operator | $ICO(a_{1},a_{2})$ |  Determines if a given number falls within a specified interval, crucial for boundary verification.
Rectangle Inclusion Operator | $RIO(R)$ |  Verifies the inclusion of a point within the boundaries of a rectangle, fundamental in obstacle avoidance.
Multiple Rectangles Inclusion Operator | $MRIO(\\{R_{i}\\}_{i=1}^{m})$ |  Extends the functionality of $RIO$ to assess inclusion within multiple rectangular obstacles simultaneously.
Quantum Threshold Comparator | $\hat{T}$ |  Evaluates whether a given value exceeds a specified threshold, used in distance calculations.
Quantum Negation Operator | $\hat{N}$ |  Performs negation operations on quantum states, essential for computing absolute differences.
Inplace Quantum Adder | $Add_{\text{in}}(k)$ |  Adds a constant $k$ to a quantum state, crucial for cumulative calculations.
General Quantum Adder | $Add_{\text{in}}$ |  Facilitates general addition operations between quantum states.
Absolute Difference Operator | $AbsDiff(k)$ |  Computes the absolute difference between quantum states, significant in distance evaluations.
Quantum Square Adder | $AddSqr_{\text{in}}$ |  Executes the square addition operation, pivotal in distance and area calculations.
Quantum Euclidean distance | $ED_{\text{in}}(c_{1},c_{2})$ |  Executes the Euclidean distance.
Quantum Vector Cross Product | $VCP$ |  Executes the vector cross product between two vectors.
Table 2: Summary of quantum operators developed for the quantum algorithm.
Each operator is integral to the various stages of spatial discretization in
the presence of obstacles.

With the improvement shown with the proposed algorithm, we pretend to push the
boundaries of what is achievable with quantum computing; the implications of
this research extend far beyond the immediate results, promising a new horizon
of possibilities in various applications requiring spatial analysis and path
planning.

##  IX conclusion

Our work introduces an innovative quantum algorithm designed to address the
generalized problem of spatial discretization, particularly in environments
peppered with obstacles of varying geometries, such as rectangles, circles,
and polygons. At the core of our algorithm lies an array of meticulously
crafted quantum operators, each tailored to navigate the complexities of such
spatial arrangements. Our approach not only achieves a quadratic enhancement
in efficiency compared to classical methods but also signifies a remarkable
advancement in computational geometry and quantum computing. The pronounced
superiority of our quantum algorithm, in terms of performance, is compellingly
illustrated in Figure (17), underscoring its potential to revolutionize
spatial analysis in complex settings.

The quantum operators developed, such as the Interval Check Operator (ICO),
Rectangle Inclusion Operator (RIO), and Quantum Threshold Comparator
($\hat{T}$), among others, are instrumental in processing and analyzing
spatial data with unparalleled efficiency. These operators showcase the
potential of quantum computing to transform tasks that are traditionally
challenging due to computational intensity and precision requirements.

Our empirical results, obtained through simulations in the PennyLane quantum
software library, validate the practical effectiveness of our algorithm. The
comparative analysis against classical approaches highlights the quantum
advantage regarding speed and efficiency and demonstrates the algorithm’s
viability within the current quantum computing landscape (17).

As we stand at the cusp of the quantum era, this research contributes
significantly to the emerging field of quantum computational geometry. It
paves the way for future explorations and applications of quantum algorithms
in various domains requiring spatial discretization. The implications of this
study extend beyond theoretical advancements; they offer insights into
potential real-world applications, from urban planning and autonomous
navigation to complex simulations in medicine and machine learning.

Our work underscores the transformative potential of quantum algorithms in
addressing complex geometric problems. It opens new horizons for quantum-
enhanced solutions in computational tasks, setting a benchmark for future
research in quantum computational geometry and related fields.

## Code

The Python code implementing the operators and reproducing the figures
discussed herein is available in the accompanying GitHub repository. The code
provides the foundational algorithms enabling in-depth exploration and
adaptation of the operators. The code can be accessed at
https://github.com/pifparfait/Quantum-improvement-in-Spatial-Discretization.

## Acknowledgements

The authors thank Guillermo Alonso de Linaje for the discussions and
consideration during the experiments.

## Compliance with Ethics Guidelines

Funding: This research received no external funding. Institutional review:
This article contains no studies with human or animal subjects. Informed
consent: Informed consent was obtained from all participants in the study.
Data availability: Data sharing is not applicable. No new data were created or
analyzed in this study. Data sharing does not apply to this article.

##  Appendix A Comparative Analysis of Classical and Quantum Oracle Efficacy

We compare the application frequency of the function $f$, which determines
point inclusion within the feasible zone for both classical and quantum cases.
We aim to acquire $M=1000$ points within the feasible zone, where $p$
represents the probability of randomly selecting a point within this zone.
Given the total area $A_{T}$ and the feasible area $A_{F}$, the probability
$p$ is given by $p=\frac{A_{F}}{A_{T}}$. Here, we calculate each case’s
expected number of function applications $f$.

###  A.1 Classical Case

In the classical scenario, we want to sample $M$ points within the feasible
zone, with $p$ being the probability of a point falling. The expected number
of Oracle applications is $\frac{M}{p}$.

If $X_{i}$ is a Bernoulli random variable taking values in $\\{0,1\\}$ with
probabilities $\\{1-p,p\\}$, the distribution modeling the required number of
trials $N$ to achieve $M$ successes is as follows. The probability that
exactly $N$ trials are necessary is given by:

$P(Y=N)=\binom{N-1}{M-1}p^{M}(1-p)^{N-M},$ (17)

which we reference as the probability distribution of $Y$ (Equation 17).

Calculating the expected value, we have:

$\displaystyle E[Y]$ $\displaystyle=\sum_{N=M}^{\infty}NP(Y=N)$
$\displaystyle=\sum_{N=M}^{\infty}N\binom{N-1}{M-1}p^{M}(1-p)^{N-M}$
$\displaystyle=\frac{Mp}{(1-p)^{M+1}}\sum_{N=M}^{\infty}\binom{N}{M}(1-p)^{N},$
(18)

where we apply the binomial theorem to arrive at the expected value (Equation
18).

$\sum_{N=M}^{\infty}\binom{N}{M}(1-p)^{N}=\frac{(1-p)^{M}}{p^{M+1}}.$ (19)

Combining (18) to (19), we arrive at:

$E[Y]=\frac{M}{p}.$ (20)

This is the expected number of queries in the classical case (Equation 20).

###  A.2 Quantum Case

In the quantum scenario, detailed in Equation 21, we seek to sample $M$ points
within the feasible zone with probability $p$. Let $CI(x)$ denote the closest
integer to a real number $x$, and let $\phi:=\arcsin(\sqrt{2p(1-p)})$.
According to Grover’s algorithm theory Grover (1996), after applying the
oracle $R$ times with $R:=CI\left(\frac{\arccos(\sqrt{p})}{\phi}\right)$, the
probability of finding a point in the correct zone is close to $1$. Hence, the
number of times we need to apply the oracle $f$ is $(R+1)*M$, with
$R\leq\sqrt{\frac{1}{p}}$. This yields:

$(R+1)M\thickapprox\frac{M}{\sqrt{p}}<\frac{M}{p},$ (21)

which is a quadratic improvement over the $\frac{M}{p}$ (20) applications
required by the classical algorithm (Equation 21).

## References

  * Skeel and Berzins (1990) Robert D Skeel and Martin Berzins, “A method for the spatial discretization of parabolic equations in one space variable,” SIAM journal on scientific and statistical computing 11, 1–32 (1990).
  * Lustgarten  _et al._ (2008) Jonathan L Lustgarten, Vanathi Gopalakrishnan, Himanshu Grover, and Shyam Visweswaran, “Improving classification performance with discretization on biomedical datasets,” in  _AMIA annual symposium proceedings_ , Vol. 2008 (American Medical Informatics Association, 2008) p. 445.
  * Grover and Dimitrakakis (2021) Divya Grover and Christos Dimitrakakis, “Adaptive belief discretization for pomdp planning,” arXiv preprint arXiv:2104.07276 (2021).
  * Atchade-Adelomou (2022) Parfait Atchade-Adelomou, “Quantum algorithms for solving hard constrained optimisation problems,”  (2022).
  * Osher and Paragios (2003) Stanley Osher and Nikos Paragios,  _Geometric level set methods in imaging, vision, and graphics_ (Springer Science & Business Media, 2003).
  * Sanyal  _et al._ (2010) Amit Sanyal, Nikolaj Nordkvist, and Monique Chyba, “An almost global tracking control scheme for maneuverable autonomous vehicles and its discretization,” IEEE Transactions on Automatic control 56, 457–462 (2010).
  * Funke  _et al._ (2016) Joseph Funke, Matthew Brown, Stephen M Erlien, and J Christian Gerdes, “Collision avoidance and stabilization for autonomous vehicles in emergency scenarios,” IEEE Transactions on Control Systems Technology 25, 1204–1216 (2016).
  * Molina  _et al._ (2016) David Molina, Julián Pérez-Beteta, Alicia Martínez-González, Juan Martino, Carlos Velásquez, Estanislao Arana, and Víctor M Pérez-García, “Influence of gray level and space discretization on brain tumor heterogeneity measures obtained from magnetic resonance images,” Computers in biology and medicine 78, 49–57 (2016).
  * Cao  _et al._ (2014) Feng Cao, Yong Ge, and Jinfeng Wang, “Spatial data discretization methods for geocomputation,” International journal of applied earth observation and geoinformation 26, 432–440 (2014).
  * Fiorini  _et al._ (2022) Lorena Fiorini, Federico Falasca, Alessandro Marucci, and Lucia Saganeiti, “Discretization of the urban and non-urban shape: Unsupervised machine learning techniques for territorial planning,” Applied Sciences 12, 10439 (2022).
  * Atchade-Adelomou  _et al._ (2021) Parfait Atchade-Adelomou, Guillermo Alonso-Linaje, Jordi Albo-Canals, and Daniel Casado-Fauli, “qrobot: A quantum computing approach in mobile robot order picking and batching problem solver optimization,” Algorithms 14 (2021), 10.3390/a14070194.
  * Adelomou  _et al._ (2020a) Atchade Parfait Adelomou, Elisabet Golobardes Ribe, and Xavier Vilasis Cardona, “Using the parameterized quantum circuit combined with variational-quantum-eigensolver (vqe) to create an intelligent social workers’ schedule problem solver,”  (2020a).
  * Gonzalez-Bermejo  _et al._ (2022) Saul Gonzalez-Bermejo, Guillermo Alonso-Linaje, and Parfait Atchade-Adelomou, “Gps: A new tsp formulation for its generalizations type qubo,” Mathematics 10, 416 (2022).
  * Atchade-Adelomou and Larson (2023) Parfait Atchade-Adelomou and Kent Larson, “Fourier series weight in quantum machine learning,” (2023), arXiv:2302.00105 [quant-ph] .
  * Parfait Adelomou  _et al._ (2020) Atchade Parfait Adelomou, Elisabet Golobardes Ribe, and Xavier Vilasis Cardona, “Using the parameterized quantum circuit combined with variational-quantum-eigensolver (vqe) to create an intelligent social workers’ schedule problem solver,” arXiv e-prints , arXiv–2010 (2020).
  * Consul-Pacareu  _et al._ (2023) S. Consul-Pacareu, R. Montaño, Kevin Rodriguez-Fernandez, Àlex Corretgé, Esteve Vilella-Moreno, Daniel Casado-Faulí, and Parfait Atchade-Adelomou, “Quantum machine learning hyperparameter search,” (2023), arXiv:2302.10298 [cs.LG] .
  * Atchade-Adelomou and Alonso-Linaje (2022) Parfait Atchade-Adelomou and Guillermo Alonso-Linaje, “Quantum-enhanced filter: Qfilter,” Soft Computing , 1–8 (2022).
  * Alonso-Linaje and Atchade-Adelomou (2021) Guillermo Alonso-Linaje and Parfait Atchade-Adelomou, “Eva: a quantum exponential value approximation algorithm,” (2021), arXiv:2106.08731 [quant-ph] .
  * Adelomou  _et al._ (2020b) Atchade Parfait Adelomou, Elisabet Golobardes Ribé, and Xavier Vilasis Cardona, “Formulation of the social workers’ problem in quadratic unconstrained binary optimization form and solve it on a quantum computer,” Journal of Computer and Communications 8, 44–68 (2020b).
  * Adelomou  _et al._ (2023) Parfait Atchade Adelomou, Daniel Casado Fauli, Elisabet Golobardes Ribé, and Xavier Vilasís-Cardona, “Quantum case-based reasoning (qcbr),” Artificial Intelligence Review 56, 2639–2665 (2023).
  * Atchade-Adelomou  _et al._ (2020) Parfait Atchade-Adelomou, Elisabet Golobardes-Ribe, and Xavier Vilasis-Cardona, “Using the parameterized quantum circuit combined with variational-quantum-eigensolver (vqe) to create an intelligent social workers’ schedule problem solver,” (2020), arXiv:2010.05863 [quant-ph] .
  * Arrazola and Xanadu (2023) Juan Miguel Arrazola and Xanadu, “From nisq to isq,” https://pennylane.ai/blog/2023/06/from-nisq-to-isq/ (2023), (accessed November 1, 2023).
  * Braun and Sambridge (1997) Jean Braun and Malcolm Sambridge, “Modelling landscape evolution on geological time scales: a new method based on irregular spatial discretization,” Basin Research 9, 27–52 (1997).
  * Kummer (2017) Florian Kummer, “Extended discontinuous galerkin methods for two-phase flows: the spatial discretization,” International Journal for Numerical Methods in Engineering 109, 259–289 (2017).
  * Bergholm  _et al._ (2022) Ville Bergholm, Josh Izaac, Maria Schuld, Christian Gogolin, Shahnawaz Ahmed, Vishnu Ajith, M. Sohaib Alam, Guillermo Alonso-Linaje, B. AkashNarayanan, Ali Asadi, Juan Miguel Arrazola, Utkarsh Azad, Sam Banning, Carsten Blank, Thomas R Bromley, Benjamin A. Cordier, Jack Ceroni, Alain Delgado, Olivia Di Matteo, Amintor Dusko, Tanya Garg, Diego Guala, Anthony Hayes, Ryan Hill, Aroosa Ijaz, Theodor Isacsson, David Ittah, Soran Jahangiri, Prateek Jain, Edward Jiang, Ankit Khandelwal, Korbinian Kottmann, Robert A. Lang, Christina Lee, Thomas Loke, Angus Lowe, Keri McKiernan, Johannes Jakob Meyer, J. A. Montañez-Barrera, Romain Moyard, Zeyue Niu, Lee James O’Riordan, Steven Oud, Ashish Panigrahi, Chae-Yeun Park, Daniel Polatajko, Nicolás Quesada, Chase Roberts, Nahum Sá, Isidor Schoch, Borun Shi, Shuli Shu, Sukin Sim, Arshpreet Singh, Ingrid Strandberg, Jay Soni, Antal Száva, Slimane Thabet, Rodrigo A. Vargas-Hernández, Trevor Vincent, Nicola Vitucci, Maurice Weber, David Wierichs, Roeland Wiersema, Moritz Willmann, Vincent Wong, Shaoming Zhang, and Nathan Killoran, “Pennylane: Automatic differentiation of hybrid quantum-classical computations,” (2022), arXiv:1811.04968 [quant-ph] .
  * Aaronson and Ambainis (2005) Scott Aaronson and Andris Ambainis, “Quantum search of spatial regions,” (2005), arXiv:quant-ph/0303041 [quant-ph] .
  * Grover (1996) Lov K Grover, “A fast quantum mechanical algorithm for database search,” in  _Proceedings of the twenty-eighth annual ACM symposium on Theory of computing_ (1996) pp. 212–219.
  * Chakraborty  _et al._ (2017) Shantanav Chakraborty, Leonardo Novo, Serena Di Giorgio, and Yasser Omar, “Optimal quantum spatial search on random temporal networks,” Physical Review Letters 119 (2017), 10.1103/physrevlett.119.220503.
  * RENYI (1959) Erdos RENYI, “On random graph,” Publicationes Mathematicate 6, 290–297 (1959).
  * Atchade-Adelomou and Gonzalez (2023) Parfait Atchade-Adelomou and Saul Gonzalez, “Efficient quantum modular arithmetics for the isq era,” (2023), arXiv:2311.08555 [quant-ph] .
  * Metropolis (1909) N Metropolis, “Beginning of the monte carlo method. 1987,” Stanislaw Ulam 1984 (1909).
  * Hansmann and Okamoto (1999) Ulrich HE Hansmann and Yuko Okamoto, “New monte carlo algorithms for protein folding,” Current opinion in structural biology 9, 177–183 (1999).
  * Şahin (2020) Engin Şahin, “Quantum arithmetic operations based on quantum fourier transform on signed integers,” International Journal of Quantum Information 18, 2050035 (2020).
  * Baugh and Wooley (1973) Charles R Baugh and Bruce A Wooley, “A two’s complement parallel array multiplication algorithm,” IEEE Transactions on computers 100, 1045–1047 (1973).