Scholarlink

<p>MaxCut is a key NP-hard combinatorial optimization problem. Quantum computing offers methods to solve such problems potentially better than classical counterparts, with the Quantum Approximate Optimization Algorithm (QAOA) being a state-of-the-art example. However, the performance of quantum methods is currently hindered by hardware noise and limited qubit volumes. We present a variational Qubit-Efficient MaxCut (QEMC) algorithm that requires only <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(O(\log N)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>O</mi> <mo>(</mo> <mi>log</mi> <mi>N</mi> <mo>)</mo> </mrow> </math></EquationSource> </InlineEquation> qubits to tackle graphs of size <i>N</i>, an exponential reduction compared to QAOA. We demonstrate cutting-edge performance for 32-node graph instances (5 qubits) on real superconducting hardware, and for graphs with up to 2048 nodes (11 qubits) via classical simulations. The QEMC algorithm is based on an innovative encoding scheme, with potentially broad applicability, that empowers it with strong noise resilience, but also enables its efficient classical simulation. As such, the QEMC algorithm provides a challenging benchmark for QAOA on noisy devices and offers a novel quantum-inspired approach.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

A Variational Qubit-Efficient MaxCut Heuristic Algorithm

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年2月16日

查看全文
  • Yovav Tene-Cohen,
  • Tomer Kelman,
  • Ohad Lev,
  • Adi Makmal

摘要

MaxCut is a key NP-hard combinatorial optimization problem. Quantum computing offers methods to solve such problems potentially better than classical counterparts, with the Quantum Approximate Optimization Algorithm (QAOA) being a state-of-the-art example. However, the performance of quantum methods is currently hindered by hardware noise and limited qubit volumes. We present a variational Qubit-Efficient MaxCut (QEMC) algorithm that requires only \(O(\log N)\) O ( log N ) qubits to tackle graphs of size N, an exponential reduction compared to QAOA. We demonstrate cutting-edge performance for 32-node graph instances (5 qubits) on real superconducting hardware, and for graphs with up to 2048 nodes (11 qubits) via classical simulations. The QEMC algorithm is based on an innovative encoding scheme, with potentially broad applicability, that empowers it with strong noise resilience, but also enables its efficient classical simulation. As such, the QEMC algorithm provides a challenging benchmark for QAOA on noisy devices and offers a novel quantum-inspired approach.