Solving the Independent Domination Problem by Quantum Approximate Optimization Algorithm

• URL: http://arxiv.org/abs/2410.17227v1
• Date: Tue, 22 Oct 2024 17:49:00 GMT
• Title: Solving the Independent Domination Problem by Quantum Approximate Optimization Algorithm
• Authors: Haoqian Pan, Changhong Lu,
• Abstract summary: 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.
• Score: 0.5919433278490629
• License:
• Abstract: In the wake of quantum computing advancements and quantum algorithmic progress, quantum algorithms are increasingly being employed to address a myriad of combinatorial optimization problems. Among these, the Independent Domination Problem (IDP), a derivative of the Domination Problem, has practical implications in various real-world scenarios. Despite this, existing classical algorithms for IDP are plagued by high computational complexity, and quantum algorithms have yet to tackle this challenge. This paper introduces a Quantum Approximate Optimization Algorithm (QAOA)-based approach to address the IDP. Utilizing IBM's qasm_simulator, we have demonstrated the efficacy of QAOA in solving IDP under specific parameter settings, with a computational complexity that surpasses that of classical methods. Our findings offer a novel avenue for the resolution of IDP.

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)
• Performance Benchmarking of Quantum Algorithms for Hard Combinatorial Optimization Problems: A Comparative Study of non-FTQC Approaches [0.0]
  This study systematically benchmarks several non-fault-tolerant quantum computing algorithms across four distinct optimization problems. Our benchmark includes noisy intermediate-scale quantum (NISQ) algorithms, such as the variational quantum eigensolver. Our findings reveal that no single non-FTQC algorithm performs optimally across all problem types, underscoring the need for tailored algorithmic strategies.
  arXiv  Detail & Related papers  (2024-10-30T08:41:29Z)
• Variational Quantum Algorithms for Combinatorial Optimization [0.571097144710995]
  Variational Algorithms (VQA) have emerged as one of the strongest candidates towards reaching practical applicability of NISQ systems. This paper explores the current state and recent developments of VQAs, emphasizing their applicability to Approximate optimization. We implement QAOA circuits with varying depths to solve the MaxCut problem on graphs with 10 and 20 nodes.
  arXiv  Detail & Related papers  (2024-07-08T22:02:39Z)
• 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)
• Quantum Annealing for Single Image Super-Resolution [86.69338893753886]
  We propose a quantum computing-based algorithm to solve the single image super-resolution (SISR) problem. The proposed AQC-based algorithm is demonstrated to achieve improved speed-up over a classical analog while maintaining comparable SISR accuracy.
  arXiv  Detail & Related papers  (2023-04-18T11:57:15Z)
• 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)
• Squeezing and quantum approximate optimization [0.6562256987706128]
  Variational quantum algorithms offer fascinating prospects for the solution of optimization problems using digital quantum computers. However, the achievable performance in such algorithms and the role of quantum correlations therein remain unclear. We show numerically as well as on an IBM quantum chip how highly squeezed states are generated in a systematic procedure.
  arXiv  Detail & Related papers  (2022-05-20T18:00:06Z)
• Implementable Hybrid Quantum Ant Colony Optimization Algorithm [0.0]
  We propose a new hybrid quantum algorithm to produce approximate solutions for NP-hard problems. We develop an improved algorithm that can be truly implemented on near-term quantum computers. The benchmarks made by simulating the noiseless quantum circuit and the experiments made on IBM quantum computers show the validity of the algorithm.
  arXiv  Detail & Related papers  (2021-07-08T13:50:51Z)
• Polynomial unconstrained binary optimisation inspired by optical simulation [52.11703556419582]
  We propose an algorithm inspired by optical coherent Ising machines to solve the problem of unconstrained binary optimization. We benchmark the proposed algorithm against existing PUBO algorithms, and observe its superior performance. The application of our algorithm to protein folding and quantum chemistry problems sheds light on the shortcomings of approxing the electronic structure problem by a PUBO problem.
  arXiv  Detail & Related papers  (2021-06-24T16:39:31Z)
• 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)
• 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.