Performance guarantees of light-cone variational quantum algorithms for the maximum cut problem

• URL: http://arxiv.org/abs/2504.12896v1
• Date: Thu, 17 Apr 2025 12:38:16 GMT
• Title: Performance guarantees of light-cone variational quantum algorithms for the maximum cut problem
• Authors: Xiaoyang Wang, Yuexin Su, Tongyang Li,
• Abstract summary: Variational quantum algorithms (VQAs) are promising to demonstrate the advantage of near-term quantum computing over classical computing.<n>We propose a light-cone VQA by choosing an optimal gate sequence of the standard VQAs.<n>We prove that the light-cone VQA with one round achieves an approximation ratio of 0.7926 for the MaxCut problem.
• Score: 12.148326652334598
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Variational quantum algorithms (VQAs) are promising to demonstrate the advantage of near-term quantum computing over classical computing in practical applications, such as the maximum cut (MaxCut) problem. However, current VQAs such as the quantum approximate optimization algorithm (QAOA) have lower performance guarantees compared to the best-known classical algorithm, and suffer from hard optimization processes due to the barren plateau problem. We propose a light-cone VQA by choosing an optimal gate sequence of the standard VQAs, which enables a significant improvement in solution accuracy while avoiding the barren plateau problem. Specifically, we prove that the light-cone VQA with one round achieves an approximation ratio of 0.7926 for the MaxCut problem in the worst case of $3$-regular graphs, which is higher than that of the 3-round QAOA, and can be further improved to 0.8333 by an angle-relaxation procedure. Finally, these performance guarantees are verified by numerical simulations and hardware demonstrations on IBM quantum devices. In a 72-qubit demonstration, the single-round light-cone VQA achieves the exact MaxCut solution whereas the $p$-round QAOA with $p=1,2,3$ only obtains approximate solutions. Furthermore, the single-round light-cone VQA derives solutions surpassing the hardness threshold in a 148-qubit demonstration while QAOA with $p=1,2,3$ does not. Our work highlights a promising route towards solving practical and classically hard problems on near-term quantum devices.

Related papers

• Branch-and-bound digitized counterdiabatic quantum optimization [39.58317527488534]
  Branch-and-bound algorithms effectively solve convex optimization problems, relying on the relaxation the objective function to obtain tight lower bounds. We propose a branch-and-bound digitized counterdiabatic quantum optimization (BB-DCQO) algorithm that addresses the relaxation difficulties.
  arXiv  Detail & Related papers  (2025-04-21T18:19:19Z)
• Solving Constrained Combinatorial Optimization Problems with Variational Quantum Imaginary Time Evolution [4.266376725904727]
  We show that VarQITE achieves significantly lower mean optimality gaps compared to other conventional methods.<n>We demonstrate that scaling the Hamiltonian can further reduce optimization costs and accelerate convergence.
  arXiv  Detail & Related papers  (2025-04-17T03:09:37Z)
• Limitations of Quantum Approximate Optimization in Solving Generic Higher-Order Constraint-Satisfaction Problems [0.0]
  The ability of the Quantum Approximate Optimization Algorithm to deliver a quantum advantage on optimization problems is still unclear. We analyze the QAOA's performance on random Max-$k$XOR as a function of $k$ and the clause-to-variable ratio. We find that reaching high levels of satisfaction would require extremely large $p$, which must be considered rather difficult both in the variational context and on near-term devices.
  arXiv  Detail & Related papers  (2024-11-28T21:39:58Z)
• Towards large-scale quantum optimization solvers with few qubits [59.63282173947468]
  We introduce a variational quantum solver for optimizations over $m=mathcalO(nk)$ binary variables using only $n$ qubits, with tunable $k>1$. We analytically prove that the specific qubit-efficient encoding brings in a super-polynomial mitigation of barren plateaus as a built-in feature.
  arXiv  Detail & Related papers  (2024-01-17T18:59:38Z)
• 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)
• Alignment between Initial State and Mixer Improves QAOA Performance for Constrained Optimization [11.445200448951072]
  Quantum alternating operator ansatz (QAOA) has a strong connection to the adiabatic algorithm. We demonstrate that the intuition from the adiabatic algorithm applies to the task of choosing the QAOA initial state.
  arXiv  Detail & Related papers  (2023-05-05T21:54:28Z)
• An Expressive Ansatz for Low-Depth Quantum Approximate Optimisation [0.23999111269325263]
  The quantum approximate optimisation algorithm (QAOA) is a hybrid quantum-classical algorithm used to approximately solve optimisation problems. While QAOA can be implemented on NISQ devices, physical limitations can limit circuit depth and decrease performance. This work introduces the eXpressive QAOA (XQAOA) that assigns more classical parameters to the ansatz to improve its performance at low depths.
  arXiv  Detail & Related papers  (2023-02-09T07:47:06Z)
• Quantum Annealing vs. QAOA: 127 Qubit Higher-Order Ising Problems on NISQ Computers [0.0]
  Quantum Alternating Operator Ansatz (QAOA) are both quantum algorithms intended for optimal solutions of optimization problems. We implement a rigorous comparison between QA on D-Wave hardware and QAOA on IBMQ hardware. We find that QA outperforms QAOA on all problem instances.
  arXiv  Detail & Related papers  (2023-01-02T04:19:46Z)
• Constrained Optimization via Quantum Zeno Dynamics [23.391640416533455]
  We introduce a technique that uses quantum Zeno dynamics to solve optimization problems with multiple arbitrary constraints, including inequalities. We show that the dynamics of quantum optimization can be efficiently restricted to the in-constraint subspace on a fault-tolerant quantum computer.
  arXiv  Detail & Related papers  (2022-09-29T18:00:40Z)
• Solving boolean satisfiability problems with the quantum approximate optimization algorithm [0.05076419064097732]
  We study the ability of QAOA to solve hard constraint satisfaction problems, as opposed to quantum computing problems. We develop analytic bounds on the average success probability of QAOA over random formulae at the satisfiability threshold. We find that for around 14 ansatz layers, QAOA matches the scaling performance of the highest-performance classical solver.
  arXiv  Detail & Related papers  (2022-08-14T20:39:48Z)
• Quantum Goemans-Williamson Algorithm with the Hadamard Test and Approximate Amplitude Constraints [62.72309460291971]
  We introduce a variational quantum algorithm for Goemans-Williamson algorithm that uses only $n+1$ qubits. Efficient optimization is achieved by encoding the objective matrix as a properly parameterized unitary conditioned on an auxilary qubit. We demonstrate the effectiveness of our protocol by devising an efficient quantum implementation of the Goemans-Williamson algorithm for various NP-hard problems.
  arXiv  Detail & Related papers  (2022-06-30T03:15:23Z)
• Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm [0.7046417074932257]
  We compare the performance of the Quantum Approximate Optimization Algorithm (QAOA) with state-of-the-art classical solvers. We find that classical solvers are capable of producing high-quality approximate solutions in linear time complexity. Other problems, such as different graphs, weighted MaxCut, maximum independent set, and 3-SAT, may be better suited for achieving quantum advantage on near-term quantum devices.
  arXiv  Detail & Related papers  (2022-06-07T20:59:19Z)
• 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)
• Improving the Performance of Deep Quantum Optimization Algorithms with Continuous Gate Sets [47.00474212574662]
  Variational quantum algorithms are believed to be promising for solving computationally hard problems. In this paper, we experimentally investigate the circuit-depth-dependent performance of QAOA applied to exact-cover problem instances. Our results demonstrate that the use of continuous gate sets may be a key component in extending the impact of near-term quantum computers.
  arXiv  Detail & Related papers  (2020-05-11T17:20:51Z)

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.