A Novel Fast Path Planning Approach for Mobile Devices using Hybrid Quantum Ant Colony Optimization Algorithm

• URL: http://arxiv.org/abs/2310.17808v1
• Date: Wed, 25 Oct 2023 09:23:00 GMT
• Title: A Novel Fast Path Planning Approach for Mobile Devices using Hybrid Quantum Ant Colony Optimization Algorithm
• Abstract summary: In emergency services, the devices must traverse in real-time, demanding speedy path planning from a TSP instance. In this paper, we propose a Hybrid Quantum Ant Colony Optimization algorithm on several TSP instances. Simulation results show promising results, thus expecting the proposed work to be important in implementing real-time path planning in quantum-enabled mobile devices.
• Score: 2.6558676135898573
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: With IoT systems' increasing scale and complexity, maintenance of a large number of nodes using stationary devices is becoming increasingly difficult. Hence, mobile devices are being employed that can traverse through a set of target locations and provide the necessary services. In order to reduce energy consumption and time requirements, the devices are required to traverse following a Hamiltonian path. This problem can be formulated as a Travelling Salesman Problem (TSP), an NP-hard problem. Moreover, in emergency services, the devices must traverse in real-time, demanding speedy path planning from the TSP instance. Among the well-known optimization techniques for solving the TSP problem, Ant Colony Optimization has a good stronghold in providing good approximate solutions. Moreover, ACO not only provides near-optimal solutions for TSP instances but can also output optimal or near-optimal solutions for many other demanding hard optimization problems. However, to have a fast solution, the next node selection, which needs to consider all the neighbors for each selection, becomes a bottleneck in the path formation step. Moreover, classical computers are constrained to generate only pseudorandom numbers. Both these problems can be solved using quantum computing techniques, i.e., the next node can be selected with proper randomization, respecting the provided set of probabilities in just a single execution and single measurement of a quantum circuit. Simulation results of the proposed Hybrid Quantum Ant Colony Optimization algorithm on several TSP instances have shown promising results, thus expecting the proposed work to be important in implementing real-time path planning in quantum-enabled mobile devices.

Related papers

• Combinatorial optimization of connected UAV communication bridges for emergency response [1.5861469511290378]
  We present a quadratic optimization problem for the strategic deployment of UAVs equipped with 5G antennas.<n>Our formulation aims to maximize signal coverage and minimize interference while ensuring network connectivity.<n>We show that the quantum adiabatic algorithm (QAA) can accurately solve small-scale instances.
  arXiv  Detail & Related papers  (2026-09-02T13:14:12Z)
• Hardware-Efficient Quantum Optimization for Transportation Networks via Compressed Adiabatic Evolution [1.409283414986451]
  Transportation systems such as urban logistics, vehicle routing, and infrastructure planning require solving large-scale optimization problems under complex constraints.<n>We develop a hardware-grounded hybrid quantum optimization framework that uses Approximate Quantum Compilation (AQC) to compress early segments of digitized adiabatic evolution into shallow circuits.<n>Results show that moderate prefix compression reduces two-qubit gate depth while maintaining or improving feasible solution, particularly for routing problems.
  arXiv  Detail & Related papers  (2026-04-28T23:45:54Z)
• Quantum Optimization Methods for the Generalized Traveling Salesman Problem [2.4029307306254513]
  This paper studies quantum optimization baselines for the Generalized Traveling Salesman Problem (GTSP)<n>We propose a novel GTSP QUBO formulation focused on maintaining feasible solutions for quantum annealing.<n>We implement a constrained QAOA variant using an XY-mixer, which preserves the stepwise Hamming weight in the ideal circuit model.
  arXiv  Detail & Related papers  (2026-04-28T11:58:35Z)
• Hybrid Classical--Quantum Optimization of Wireless Routing Using QAOA and Quantum Walks [0.0]
  This paper investigates the use of hybrid classical--quantum methods for wireless routing.<n>The potential value of quantum routing lies in the treatment of difficult subproblems rather than end-to-end replacement of classical routing.
  arXiv  Detail & Related papers  (2026-04-01T01:48:57Z)
• Quantum Approaches to Urban Logistics: From Core QAOA to Clustered Scalability [0.0]
  The Traveling Salesman Problem (TSP) is a fundamental challenge in optimization, widely applied in logistics and transportation.<n>Traditional algorithms often struggle to produce high-quality solutions within reasonable timeframes.<n>This study investigates the potential of the Quantum Approximate Optimization Algorithm (QAOA), a hybrid quantum-classical method.
  arXiv  Detail & Related papers  (2025-12-11T17:00:24Z)
• A Non-Variational Quantum Approach to the Job Shop Scheduling Problem [0.3078691410268859]
  We introduce Iterative-QAOA, a variant of QAOA designed to mitigate near-term hardware limitations.<n>We benchmark the algorithm on Just-in-Time Job Shop Scheduling Problem (JIT-JSSP) instances on IonQ Forte Generation QPUs.<n>We find that Iterative-QAOA robustly converges to find optimal solutions as well as high-quality, near-optimal solutions for all problem instances evaluated.
  arXiv  Detail & Related papers  (2025-10-30T16:14:13Z)
• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  This paper proposes a novel combination of constraint encoding methods for the Quantum Approximate Optimization Ansatz.<n>One-hot constraints are enforced through $XY$-mixers that restrict the search space to the feasible sub-space naturally.<n>Since $XY$-mixers restrict the search space, specific state vector entries are always zero and can be omitted from the simulation, saving valuable memory and computing resources.
  arXiv  Detail & Related papers  (2025-06-03T17:46:53Z)
• Solving the Traveling Salesman Problem via Different Quantum Computing Architectures [0.0]
  We study the application of emerging photonic and quantum computing architectures to solving the Traveling Salesman Problem (TSP) Gate-based quantum computers demonstrated accurate results for small TSP instances in simulation. Ising-based architectures show improved scalability for larger problem sizes.
  arXiv  Detail & Related papers  (2025-02-24T23:37:19Z)
• Quantum evolutionary algorithm for TSP combinatorial optimisation problem [0.0]
  This paper implements a new way of solving a problem called the traveling salesman problem (TSP) using quantum genetic algorithm (QGA) We compared how well this new approach works to the traditional method known as a classical genetic algorithm (CGA)
  arXiv  Detail & Related papers  (2024-09-20T08:27:42Z)
• Bayesian Parameterized Quantum Circuit Optimization (BPQCO): A task and hardware-dependent approach [49.89480853499917]
  Variational quantum algorithms (VQA) have emerged as a promising quantum alternative for solving optimization and machine learning problems. In this paper, we experimentally demonstrate the influence of the circuit design on the performance obtained for two classification problems. We also study the degradation of the obtained circuits in the presence of noise when simulating real quantum computers.
  arXiv  Detail & Related papers  (2024-04-17T11:00:12Z)
• Assessing Quantum Computing Performance for Energy Optimization in a Prosumer Community [1.072460284847973]
  "Prosumer problem" is the problem of scheduling the household loads on the basis of the user needs, the electricity prices, and the availability of local renewable energy. Quantum computers can offer a significant breakthrough in treating this problem thanks to the intrinsic parallel nature of quantum operations. We report on an extensive set of experiments, on simulators and real quantum hardware, for different problem sizes.
  arXiv  Detail & Related papers  (2023-11-17T15:48:51Z)
• Quantum-Assisted Solution Paths for the Capacitated Vehicle Routing Problem [0.0]
  We discuss the Capacitated Vehicle Problem (CVRP) or its reduced variant, the Travelling Salesperson Problem (TSP) Even with today's most powerful classical algorithms, the CVRP is challenging to solve classically. Quantum computing may offer a way to improve the time to solution.
  arXiv  Detail & Related papers  (2023-04-19T13:03:50Z)
• Fermionic Quantum Approximate Optimization Algorithm [11.00442581946026]
  We propose fermionic quantum approximate optimization algorithm (FQAOA) for solving optimization problems with constraints. FQAOA tackle the constrains issue by using fermion particle number preservation to intrinsically impose them throughout QAOA. We provide a systematic guideline for designing the driver Hamiltonian for a given problem Hamiltonian with constraints.
  arXiv  Detail & Related papers  (2023-01-25T18:36:58Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  Multi-Object Tracking (MOT) is most often approached in the tracking-by-detection paradigm, where object detections are associated through time. As these optimization problems are often NP-hard, they can only be solved exactly for small instances on current hardware. We show that our approach is competitive compared with state-of-the-art optimization-based approaches, even when using of-the-shelf integer programming solvers.
  arXiv  Detail & Related papers  (2022-02-17T18:59:20Z)
• Scaling Quantum Approximate Optimization on Near-term Hardware [49.94954584453379]
  We quantify scaling of the expected resource requirements by optimized circuits for hardware architectures with varying levels of connectivity. We show the number of measurements, and hence total time to synthesizing solution, grows exponentially in problem size and problem graph degree. These problems may be alleviated by increasing hardware connectivity or by recently proposed modifications to the QAOA that achieve higher performance with fewer circuit layers.
  arXiv  Detail & Related papers  (2022-01-06T21:02:30Z)
• Data-Driven Random Access Optimization in Multi-Cell IoT Networks with NOMA [78.60275748518589]
  Non-orthogonal multiple access (NOMA) is a key technology to enable massive machine type communications (mMTC) in 5G networks and beyond. In this paper, NOMA is applied to improve the random access efficiency in high-density spatially-distributed multi-cell wireless IoT networks. A novel formulation of random channel access management is proposed, in which the transmission probability of each IoT device is tuned to maximize the geometric mean of users' expected capacity.
  arXiv  Detail & Related papers  (2021-01-02T15:21:08Z)
• Adaptive pruning-based optimization of parameterized quantum circuits [62.997667081978825]
  Variisy hybrid quantum-classical algorithms are powerful tools to maximize the use of Noisy Intermediate Scale Quantum devices. We propose a strategy for such ansatze used in variational quantum algorithms, which we call "Efficient Circuit Training" (PECT) Instead of optimizing all of the ansatz parameters at once, PECT launches a sequence of variational algorithms.
  arXiv  Detail & Related papers  (2020-10-01T18:14:11Z)
• TIGER: Topology-aware Assignment using Ising machines Application to Classical Algorithm Tasks and Quantum Circuit Gates [2.4047296366832307]
  A mapping problem exists in gate-based quantum computing where the objective is to map tasks to gates in a topology fashion. Existing task approaches are either or based on physical optimization algorithms, providing different speed and solution quality trade-offs. We propose an algorithm that allows solving the topology-aware assignment problem using Ising machines.
  arXiv  Detail & Related papers  (2020-09-21T19:46:59Z)
• Space-efficient binary optimization for variational computing [68.8204255655161]
  We show that it is possible to greatly reduce the number of qubits needed for the Traveling Salesman Problem. We also propose encoding schemes which smoothly interpolate between the qubit-efficient and the circuit depth-efficient models.
  arXiv  Detail & Related papers  (2020-09-15T18:17:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.