Solving the Perfect Domination Problem by Quantum Approximate Optimization Algorithm with Small Layers

• URL: http://arxiv.org/abs/2411.12608v1
• Date: Tue, 19 Nov 2024 16:12:36 GMT
• Title: Solving the Perfect Domination Problem by Quantum Approximate Optimization Algorithm with Small Layers
• Authors: Haoqian Pan, Changhong Lu, Yuqing Zheng,
• Abstract summary: The Perfect Domination Problem ( PDP) has significant applications in real-world scenarios, such as wireless and social networks. With the recent advancements in quantum computing, there has been a surge in the development of quantum algorithms aimed at addressing NP-complete problems. This study represents a pioneering effort to apply quantum algorithms to the PDP, as well as their efficacy in solving it.
• Score: 1.345977710890196
• License:
• Abstract: The Perfect Domination Problem (PDP), a classical challenge in combinatorial optimization, has significant applications in real-world scenarios, such as wireless and social networks. Over several decades of research, the problem has been demonstrated to be NP-complete across numerous graph classes. With the recent advancements in quantum computing, there has been a surge in the development of quantum algorithms aimed at addressing NP-complete problems, including the Quantum Approximate Optimization Algorithm (QAOA). However, the applicability of quantum algorithms to the PDP, as well as their efficacy in solving it, remains largely unexplored. This study represents a pioneering effort to apply QAOA, with a limited number of layers, to address the PDP. Comprehensive testing and analysis were conducted across 420 distinct parameter combinations. Experimental results indicate that QAOA successfully identified the correct Perfect Dominating Set (PDS) in 82 cases, including 17 instances where the optimal PDS was computed. Furthermore, it was observed that with appropriate parameter settings, the approximation ratio could achieve a value close to 0.9. These findings underscore the potential of QAOA as a viable approach for solving the PDP, signifying an important milestone that introduces this problem into the realm of quantum computing.

Related papers

• Application of Quantum Approximate Optimization Algorithm in Solving the Total Domination Problem [0.5266869303483376]
  Total Domination Problem (TDP) is a classic and critical example in the field. Recent advancements in quantum computing have led to significant research into applying quantum algorithms to optimization problems. We present a pioneering application of the Quantum Approximate Optimization Algorithm (QAOA) to tackle the TDP.
  arXiv  Detail & Related papers  (2024-11-01T05:05:14Z)
• Solving the Independent Domination Problem by Quantum Approximate Optimization Algorithm [0.5919433278490629]
  Independent Domination Problem (IDP) has practical implications in various real-world scenarios. Existing classical algorithms for IDP are plagued by high computational complexity. This paper introduces a Quantum Approximate Optimization (QAOA)-based approach to address the IDP.
  arXiv  Detail & Related papers  (2024-10-22T17:49:00Z)
• Distributed Quantum Approximate Optimization Algorithm on Integrated High-Performance Computing and Quantum Computing Systems for Large-Scale Optimization [1.7099366779394252]
  Quantum approximated optimization algorithm (QAOA) has shown promise for solving optimization problems by providing quantum speedup on gate-based quantum computing systems. We propose a distributed QAOA (DQAOA), which leverages a high-performance computing-quantum computing integrated system. We successfully optimize photonic structures using AL-DQAOA, indicating that solving real-world optimization problems using gate-based quantum computing is feasible with our strategies.
  arXiv  Detail & Related papers  (2024-07-29T17:42:25Z)
• PO-QA: A Framework for Portfolio Optimization using Quantum Algorithms [4.2435928520499635]
  Portfolio Optimization (PO) is a financial problem aiming to maximize the net gains while minimizing the risks in a given investment portfolio. We propose a novel scalable framework, denoted PO-QA, to investigate the variation of quantum parameters. Our results provide effective insights into comprehending PO from the lens of Quantum Machine Learning.
  arXiv  Detail & Related papers  (2024-07-29T10:26:28Z)
• 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)
• A Review on Quantum Approximate Optimization Algorithm and its Variants [47.89542334125886]
  The Quantum Approximate Optimization Algorithm (QAOA) is a highly promising variational quantum algorithm that aims to solve intractable optimization problems. This comprehensive review offers an overview of the current state of QAOA, encompassing its performance analysis in diverse scenarios. We conduct a comparative study of selected QAOA extensions and variants, while exploring future prospects and directions for the algorithm.
  arXiv  Detail & Related papers  (2023-06-15T15:28:12Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• Decomposition of Matrix Product States into Shallow Quantum Circuits [62.5210028594015]
  tensor network (TN) algorithms can be mapped to parametrized quantum circuits (PQCs) We propose a new protocol for approximating TN states using realistic quantum circuits. Our results reveal one particular protocol, involving sequential growth and optimization of the quantum circuit, to outperform all other methods.
  arXiv  Detail & Related papers  (2022-09-01T17:08:41Z)
• Analyzing the behaviour of D'WAVE quantum annealer: fine-tuning parameterization and tests with restrictive Hamiltonian formulations [1.035593890158457]
  D'WAVE Systems' quantum-annealer can be use to solve optimization problems by translating them into an energy minimization problem. This study is focused on providing useful insights and information into the behaviour of the quantum-annealer when addressing real-world optimization problems.
  arXiv  Detail & Related papers  (2022-07-01T07:54:26Z)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)

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.