Progressive Quantum Algorithm for Maximum Independent Set with Quantum Alternating Operator Ansatz

• URL: http://arxiv.org/abs/2405.04303v3
• Date: Tue, 08 Apr 2025 02:46:21 GMT
• Title: Progressive Quantum Algorithm for Maximum Independent Set with Quantum Alternating Operator Ansatz
• Authors: Xiao-Hui Ni, Ling-Xiao Li, Yan-Qi Song, Zheng-Ping Jin, Su-Juan Qin, Fei Gao,
• Abstract summary: We propose a Progressive Quantum Algorithm (PQA) with QAOA+ ansatz to solve the Maximum Independent Set (MIS) problem using fewer qubits.<n>PQA requires only $5.565%$ ($2.170%$) of the qubits and $17.59%$ ($6.430%$) of the runtime compared with directly solving the original problem.
• Score: 7.693541968022234
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Hadfield et al. proposed a novel Quantum Alternating Operator Ansatz algorithm (QAOA+), and this algorithm has wide applications in solving constrained combinatorial optimization problems (CCOPs) because of the advantages of QAOA+ ansatz in constructing a feasible solution space. In this paper, we propose a Progressive Quantum Algorithm (PQA) with QAOA+ ansatz to solve the Maximum Independent Set (MIS) problem using fewer qubits. The core idea of PQA is to construct a subgraph that is likely to contain the MIS solution of the target graph and then solve the MIS problem on this subgraph to obtain an approximate solution. To construct such a subgraph, PQA starts with a small-scale initial subgraph and progressively expands its graph size utilizing heuristic expansion strategies. After each expansion, PQA solves the MIS problem on the newly generated subgraph. In each run, PQA repeats the expansion and solving process until a predefined stopping condition is reached. Simulation results demonstrate that to achieve an approximation ratio of 0.95, PQA requires only $5.565\%$ ($2.170\%$) of the qubits and $17.59\%$ ($6.430\%$) of the runtime compared with directly solving the original problem using QAOA+ on Erd\H{o}s-R\'enyi (3-regular) graphs, highlighting the efficiency of PQA.

Related papers

• Phantom Edges in the Problem Hamiltonian: A Method for Increasing Performance and Graph Visibility for QAOA [0.0]
  We present a new QAOA ansatz that introduces only one additional parameter to the standard ansatz. We derive a general formula for our new ansatz at $p=1$ and analytically show an improvement in the approximation ratio for cycle graphs.
  arXiv  Detail & Related papers  (2024-11-07T22:20:01Z)
• Modified Recursive QAOA for Exact Max-Cut Solutions on Bipartite Graphs: Closing the Gap Beyond QAOA Limit [4.364124102844566]
  Quantum Approximate Optimization Algorithm (QAOA) is a quantum-classical hybrid algorithm proposed with the goal of approximately solving optimization problems such as the MAX-CUT problem. We first analytically prove the performance limitations of level-1 QAOA in solving the MAX-CUT problem on bipartite graphs. Second, we demonstrate that Recursive QAOA (RQAOA), which reduces graph size using QAOA as a subroutine, outperforms the level-1 QAOA. Finally, we show that RQAOA with a restricted parameter regime can fully address these limitations.
  arXiv  Detail & Related papers  (2024-08-23T16:35:47Z)
• Towards Less Greedy Quantum Coalition Structure Generation in Induced Subgraph Games [3.6021182997326022]
  The transition to 100% renewable energy requires new techniques for managing energy networks, such as dividing them into sensible subsets of prosumers called micro-grids. Doing so in an optimal manner is a difficult optimization problem, as it can be abstracted to the Coalition Structure Generation problem in Induced Subgraph Games. This work proposes several less greedy QA-based approaches and investigates whether any of them can outperform GCS-Q in terms of solution quality.
  arXiv  Detail & Related papers  (2024-08-08T10:54:56Z)
• Hybrid Classical-Quantum Simulation of MaxCut using QAOA-in-QAOA [0.0]
  In this work, an implementation of the QAOA2 method for the scalable solution of the MaxCut problem is presented. The limits of the Goemans-Williamson (GW) algorithm as a purely classical alternative to QAOA are investigated. Results from large-scale simulations of up to 33 qubits are presented, showing the advantage of QAOA in certain cases and the efficiency of the implementation.
  arXiv  Detail & Related papers  (2024-06-25T09:02:31Z)
• An Analysis of Quantum Annealing Algorithms for Solving the Maximum Clique Problem [49.1574468325115]
  We analyse the ability of quantum D-Wave annealers to find the maximum clique on a graph, expressed as a QUBO problem. We propose a decomposition algorithm for the complementary maximum independent set problem, and a graph generation algorithm to control the number of nodes, the number of cliques, the density, the connectivity indices and the ratio of the solution size to the number of other nodes.
  arXiv  Detail & Related papers  (2024-06-11T04:40:05Z)
• QAOA-in-QAOA: solving large-scale MaxCut problems on small quantum machines [81.4597482536073]
  Quantum approximate optimization algorithms (QAOAs) utilize the power of quantum machines and inherit the spirit of adiabatic evolution. We propose QAOA-in-QAOA ($textQAOA2$) to solve arbitrary large-scale MaxCut problems using quantum machines. Our method can be seamlessly embedded into other advanced strategies to enhance the capability of QAOAs in large-scale optimization problems.
  arXiv  Detail & Related papers  (2022-05-24T03:49:10Z)
• Efficient Algorithms for Planning with Participation Constraints [74.74967476995572]
  We consider the problem of planning with participation constraints introduced in [Zhang et al., 2022] In this problem, a principal chooses actions in a decision process, resulting in separate utilities for the principal and the agent. We provide the first-time exact algorithm for this problem for finite-horizon settings, where previously only an additive $varepsilon$-approximation was known.
  arXiv  Detail & Related papers  (2022-05-16T15:47:41Z)
• 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)
• Polyak-Ruppert Averaged Q-Leaning is Statistically Efficient [90.14768299744792]
  We study synchronous Q-learning with Polyak-Ruppert averaging (a.k.a., averaged Q-leaning) in a $gamma$-discounted MDP. We establish normality for the iteration averaged $barboldsymbolQ_T$. In short, our theoretical analysis shows averaged Q-Leaning is statistically efficient.
  arXiv  Detail & Related papers  (2021-12-29T14:47:56Z)
• Solving correlation clustering with QAOA and a Rydberg qudit system: a full-stack approach [94.37521840642141]
  We study the correlation clustering problem using the quantum approximate optimization algorithm (QAOA) and qudits. Specifically, we consider a neutral atom quantum computer and propose a full stack approach for correlation clustering. We show the qudit implementation is superior to the qubit encoding as quantified by the gate count.
  arXiv  Detail & Related papers  (2021-06-22T11:07:38Z)
• 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)
• Large-scale Quantum Approximate Optimization via Divide-and-Conquer [8.733794945008562]
  We propose a Divide-and-Conquer QAOA (DC-QAOA) to address the challenges for graph maximum cut (MaxCut) problem. DC-QAOA achieves 97.14% approximation ratio (20.32% higher than classical counterpart) It also reduces the time complexity of conventional QAOA from exponential to quadratic.
  arXiv  Detail & Related papers  (2021-02-26T03:10:30Z)
• A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm for Bilevel Optimization [112.59170319105971]
  We propose a new algorithm -- the Momentum- Single-timescale Approximation (MSTSA) -- for tackling problems. MSTSA allows us to control the error in iterations due to inaccurate solution to the lower level subproblem.
  arXiv  Detail & Related papers  (2021-02-15T07:10:33Z)
• Provably Efficient Model-Free Algorithm for MDPs with Peak Constraints [38.2783003051101]
  This paper considers the peak Constrained Markov Decision Process (PCMDP), where the agent chooses the policy to maximize total reward in the finite horizon as well as satisfy constraints at each epoch with probability 1. We propose a model-free algorithm that converts PCMDP problem to an unconstrained problem and a Q-learning based approach is applied.
  arXiv  Detail & Related papers  (2020-03-11T23:23:29Z)
• Differentially Quantized Gradient Methods [53.3186247068836]
  We show that Differentially Quantized Gradient Descent (DQ-GD) attains a linear contraction factor of $maxsigma_mathrmGD, rhon 2-R$. No algorithm within a certain class can converge faster than $maxsigma_mathrmGD, 2-R$.
  arXiv  Detail & Related papers  (2020-02-06T20:40:53Z)

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.