• Abstract 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)) 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.
Article Summaries:
- Summary
Researchers have introduced the Variational Qubit‑Efficient MaxCut (QEMC) algorithm, a new heuristic for solving the NP‑hard MaxCut problem. Unlike the standard Quantum Approximate Optimization Algorithm (QAOA), QEMC requires only (O(\log N)) qubits to handle graphs of size (N), an exponential reduction in qubit count. The team demonstrated the method on a 32‑node graph using five qubits on real superconducting hardware, and on graphs up to 2,048 nodes (11 qubits) via classical simulation. The algorithm’s novel encoding scheme offers strong noise resilience and enables efficient classical simulation, positioning QEMC as a challenging benchmark for QAOA on noisy intermediate‑scale quantum devices and a promising quantum‑inspired approach.
Sources: